<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:
    typedef long long ll;
    ll MOD=1e9+7;
    vector<ll> dp;
    string s;
    int fun(int ind)
    {
        if(ind==s.length())
        return 1;
        if(dp[ind]!=-1)
        return dp[ind];
        ll ans=0,cc=0;
        vector<int> vis(27);
        for(ll j=ind;j<=s.length();j++)
        {
            if(j==s.length() or s[j]!=s[ind])
            {
                if(j==s.length())
                {
                    ans+=(cc*fun(j));
                    ans%=MOD;
                    continue;

                }
                if(vis[s[j]-'a']!=cc)
                {
                    ans+=(cc-vis[s[j]-'a'])*fun(j);
                    ans%=MOD;
                    vis[s[j]-'a']=cc;

                }

            }
            else if(s[j]==s[ind])
            cc++;
        }
        return dp[ind]=ans;
    }
    int distinctSubseqII(string ss) {
        s=ss;
        dp.assign(s.length()+1,-1);
        map<char,ll> vis;
        int ans=0;
        for(ll i=0;i<s.length();i++)
        {
            if(vis[s[i]]==0)
            {
                ans+=fun(i);
                ans%=MOD;
                vis[s[i]]=1;

            }
        }
        return ans;

        
    }
};
21600