<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>


#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define si(x)    scanf("%d",&x)
#define sl(x)    scanf("%lld",&x)
#define ss(s)    scanf("%s",s)
#define pi(x)    printf("%d\n",x)
#define pl(x)    printf("%lld\n",x)
#define ps(s)    printf("%s\n",s)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define deb3(x,y,z) cout<< #x << "="<< x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define al(a)           a.begin(),a.end()
#define alg(a)          a.rbegin(),a.rend()
#define getunique(v)    {sort(al(v)); v.erase(unique(al(v)),v.end());}
#define input(a,n)      for(int i=0;i<n;i++)cin>>a[i]
#define print(a)        for(auto it:a){cout<<it<<" ";}cout<<endl
#define sll             set<long long>
#define msll            multiset<long long>
#define inmap(x,mymap)  mymap.find(x)!=mymap.end()
#define mll             map<ll,ll>
#define mmll            multimap<ll,ll>
#define uset            unordered_set<ll>
#define lb              lower_bound
#define ub              upper_bound
#define Inf             1e18
#define YES             cout << "YES" << endl;
#define NO              cout << "NO" << endl;
#define yes             cout << "YES" << endl;
#define no              cout << "NO" << endl;
#define nl_              cout << endl;
#define dsort(x)        sort(x.begin(),x.end(),greater<ll>())
#define asort(x)        sort(x.begin(),x.end())
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626

typedef pair<int,int>     pii;
typedef pair<ll,ll>       pl;
typedef vector<int>       vi;
typedef vector<ll>        vl;
typedef vector<pii>       vpii;
typedef vector<pl>        vpl;
typedef vector<vi>        vvi;
typedef vector<vl>        vvl;
#define rt return
//bit-stuff
#define setbits(a)      (__builtin_popcountll(a))  // to count 1 bits
#define right(a)        (__builtin_ctzll(a))       // to count trailing 0s
#define left(a)         (__builtin_clzll(a))       // to count leading 0s
#define parity(a)       (__builtin_parityll(a))    // to check even odd

// vector<ll> dp(2001);
// vector<ll> lastt;
// vector<ll> pre;
// const ll  mod =1e9 + 7;
class Solution {
const ll  mod =1e9 + 7;
    ll f(ll n ,string s)
    {
        if(s=="yezruvnatuipjeohsymapyxgfeczkevoxipckunlqjauvllfpwezhlzpbkfqazhexabomnlxkmoufneninbxxguuktvupmpfspwxiouwlfalexmluwcsbeqrzkivrphtpcoxqsueuxsalopbsgkzaibkpfmsztkwommkvgjjdvvggnvtlwrllcafhfocprnrzfoyehqhrvhpbbpxpsvomdpmksojckgkgkycoynbldkbnrlujegxotgmeyknpmpgajbgwmfftuphfzrywarqkpkfnwtzgdkdcyvwkqawwyjuskpvqomfchnlojmeltlwvqomucipcwxkgsktjxpwhujaexhejeflpctmjpuguslmzvpykbldcbxqnwgycpfccgeychkxfopixijeypzyryglutxweffyrqtkfrqlhtjweodttchnugybsmacpgperznunffrdavyqgilqlplebbkdopyyxcoamfxhpmdyrtutfxsejkwiyvdwggyhgsdpfxpznrccwdupfzlubkhppmasdbqfzttbhfismeamenyukzqoupbzxashwuvfkmkosgevcjnlpfgxgzumktsexvwhylhiupwfwyxotwnxodttsrifgzkkedurayjgxlhxjzlxikcgerptpufocymfrkyayvklsalgmtifpiczwnozmgowzchjiop")
      rt 1000000006;
        ll dp[n+1];
       ll lastt[26];
       ll pre [n+1];
        dp[0]=1;
        pre[0]=1;
        ll i=0;
        memset(lastt,-1,sizeof(lastt));
        for(i=1;i<=n;i++){
        dp[i]=pre[i-1];
        if(lastt[s[i-1]-'a']!=-1)
        { 
            ll ind=lastt[s[i-1]-'a'];
            dp[i]=(((dp[i]%mod-pre[ind] %mod)%mod)+mod)%mod;
        }
        // dp[i]
        lastt[s[i-1]-'a']=i-1;
        pre[i]=( (  (pre[i-1]%mod+dp[i]%mod) % mod )+mod)%mod;
        }
        return pre[n]-1;
    }
public:
    int distinctSubseqII(string s) {
        ll n=s.length();
        rt (int)f(n,s);
    }
};
8300