<p>Given a string s, return <em>the number of <strong>distinct non-empty subsequences</strong> of</em> <code>s</code>. Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>
A <strong>subsequence</strong> of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., <code>&quot;ace&quot;</code> is a subsequence of <code>&quot;<u>a</u>b<u>c</u>d<u>e</u>&quot;</code> while <code>&quot;aec&quot;</code> is not.
<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abc&quot;
<strong>Output:</strong> 7
<strong>Explanation:</strong> The 7 distinct subsequences are &quot;a&quot;, &quot;b&quot;, &quot;c&quot;, &quot;ab&quot;, &quot;ac&quot;, &quot;bc&quot;, and &quot;abc&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aba&quot;
<strong>Output:</strong> 6
<strong>Explanation:</strong> The 6 distinct subsequences are &quot;a&quot;, &quot;b&quot;, &quot;ab&quot;, &quot;aa&quot;, &quot;ba&quot;, and &quot;aba&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aaa&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> The 3 distinct subsequences are &quot;a&quot;, &quot;aa&quot; and &quot;aaa&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 2000</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

class Solution
{
public:
    int distinctSubseqII(std::string s)
    {
        // dp[i][c]: Num distinct subsequences in s[...i], ending with c.
        auto n = static_cast<const int>(s.size());
        std::vector dp(n + 1, std::vector<int>(26, 0));
        
        // s[i] != 'c':
        // dp[i][c] == dp[i - 1][c]
        // s[i] == 'c':
        // dp[i][c] == A + B - AB
        // A: using chars before s[i], ending with c, dp[i - 1][c]
        // B: subseq ending at s[i], sum(dp[i - 1]) + 1
        // AB == A because A is B's subset. 
        // dp[i][c] == sum(dp[i - 1]) + 1

        for (int i = 1; i <= n; ++i)
        {
            for (int c = 0; c < 26; ++c)
            {
                if (s[i - 1] - 'a' == c)
                {
                    dp[i][c] = 1;

                    for (int k = 0; k < 26; ++k)
                    {
                        dp[i][c] = (dp[i][c] + dp[i - 1][k]) % p;
                    }
                }
                else
                {
                    dp[i][c] = dp[i - 1][c];
                }
            }
        }

        return std::reduce(
            dp.back().cbegin(), 
            dp.back().cend(), 
            0, 
            [](int a, int b)
            {
                return (a + b) % p;
            }
        );
    }

private:
    static constexpr int p = 1'000'000'007;
};
21100