#include<bits/stdc++.h>
#define int long long
using namespace std;

class RollingHash{
public:
  typedef long long ll;
  ll B, mod;  //B: ハッシュ基数
  int n;
  string s;
  vector<ll> hash;
  vector<ll> k;

  RollingHash():n(-1){};
  RollingHash(string s,ll B = 1777771,ll mod = 1e9 + 7):
    B(B),mod(mod),n(s.size()),s(s),hash(n+1),k(n+1)
  {
    for(int i=0;i<n;i++) hash[i+1] = (hash[i] * B % mod + s[i]) % mod;
    k[0] = 1;
    for(int i=1;i<=n;i++) k[i] = (k[i-1] * B) % mod;
  }

  ll get(int l,int r){ //[l, r)
    assert(0<=l && r<=n && l<=r);
    return (mod + hash[r] - hash[l] * k[r-l] % mod) % mod;
  }
  
  //hash[a]とB.hash[b]からみて何文字一致してるか。
  int count(int a, RollingHash &B, int b){
    int L = 0, R = min( n - a, B.n - b ) + 1;
    while( L + 1 < R ){
      int M = ( L + R ) / 2;
      get( a, a + M ) != B.get( b, b + M ) ? R = M : L = M;
    }
    return L;
  }
};

signed main(){
  int n,mod=1e9+7;
  string s,t;
  cin>>n;
  map<int,vector<int> > mp;
  vector<int> v[1000],o;
  for(int i=0;i<n;i++){
    cin>>s;
    RollingHash tp=RollingHash(s);
    mp[s.size()].push_back(tp.get(0,0+s.size()));    
  }
  
  int m=0;
  for(auto p : mp){
    o.push_back(p.first);
    for(auto pp : p.second)v[m].push_back(pp);
    sort(v[m].begin(),v[m].end());
    m++;
  }
  cin>>t;
  RollingHash rh=RollingHash(t);
  int dp[100001]={};
  dp[0]=1;
  
  for(int i=0;i<t.size();i++){
    for(int j=0;j<m;j++){
      if(i+o[j]>t.size())break;
      int hs=rh.get(i,i+o[j]);
      auto I=lower_bound(v[j].begin(),v[j].end(),hs);
      if(I==v[j].end()||*I!=hs)continue;
      (dp[i+o[j]]+=dp[i])%=mod;
    }
  }
  cout<<dp[t.size()]<<endl;
  return 0;
}


### Prompt

Please provide a CPP coded solution to the problem described below:

You are given a string $t$ and a set $S$ of $N$ different strings. You need to separate $t$ such that each part is included in $S$.

For example, the following 4 separation methods satisfy the condition when $t = abab$ and $S = \\{a, ab, b\\}$.

* $a,b,a,b$
* $a,b,ab$
* $ab,a,b$
* $ab,ab$



Your task is to count the number of ways to separate $t$. Because the result can be large, you should output the remainder divided by $1,000,000,007$.



Input

The input consists of a single test case formatted as follows.


$N$
$s_1$
:
$s_N$
$t$


The first line consists of an integer $N$ ($1 \leq N \leq 100,000$) which is the number of the elements of $S$. The following $N$ lines consist of $N$ distinct strings separated by line breaks. The $i$-th string $s_i$ represents the $i$-th element of $S$. $s_i$ consists of lowercase letters and the length is between $1$ and $100,000$, inclusive. The summation of length of $s_i$ ($1 \leq i \leq N$) is at most $200,000$. The next line consists of a string $t$ which consists of lowercase letters and represents the string to be separated and the length is between $1$ and $100,000$, inclusive.

Output

Calculate the number of ways to separate $t$ and print the remainder divided by $1,000,000,007$.

Examples

Input

3
a
b
ab
abab


Output

4


Input

3
a
b
c
xyz


Output

0


Input

7
abc
ab
bc
a
b
c
aa
aaabcbccababbc


Output

160


Input

10
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaaa
aaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa


Output

461695029

### Response

```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;

class RollingHash{
public:
  typedef long long ll;
  ll B, mod;  //B: ハッシュ基数
  int n;
  string s;
  vector<ll> hash;
  vector<ll> k;

  RollingHash():n(-1){};
  RollingHash(string s,ll B = 1777771,ll mod = 1e9 + 7):
    B(B),mod(mod),n(s.size()),s(s),hash(n+1),k(n+1)
  {
    for(int i=0;i<n;i++) hash[i+1] = (hash[i] * B % mod + s[i]) % mod;
    k[0] = 1;
    for(int i=1;i<=n;i++) k[i] = (k[i-1] * B) % mod;
  }

  ll get(int l,int r){ //[l, r)
    assert(0<=l && r<=n && l<=r);
    return (mod + hash[r] - hash[l] * k[r-l] % mod) % mod;
  }
  
  //hash[a]とB.hash[b]からみて何文字一致してるか。
  int count(int a, RollingHash &B, int b){
    int L = 0, R = min( n - a, B.n - b ) + 1;
    while( L + 1 < R ){
      int M = ( L + R ) / 2;
      get( a, a + M ) != B.get( b, b + M ) ? R = M : L = M;
    }
    return L;
  }
};

signed main(){
  int n,mod=1e9+7;
  string s,t;
  cin>>n;
  map<int,vector<int> > mp;
  vector<int> v[1000],o;
  for(int i=0;i<n;i++){
    cin>>s;
    RollingHash tp=RollingHash(s);
    mp[s.size()].push_back(tp.get(0,0+s.size()));    
  }
  
  int m=0;
  for(auto p : mp){
    o.push_back(p.first);
    for(auto pp : p.second)v[m].push_back(pp);
    sort(v[m].begin(),v[m].end());
    m++;
  }
  cin>>t;
  RollingHash rh=RollingHash(t);
  int dp[100001]={};
  dp[0]=1;
  
  for(int i=0;i<t.size();i++){
    for(int j=0;j<m;j++){
      if(i+o[j]>t.size())break;
      int hs=rh.get(i,i+o[j]);
      auto I=lower_bound(v[j].begin(),v[j].end(),hs);
      if(I==v[j].end()||*I!=hs)continue;
      (dp[i+o[j]]+=dp[i])%=mod;
    }
  }
  cout<<dp[t.size()]<<endl;
  return 0;
}


```