#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,unsigned long long>P;

int trie[200009][27],n,c,dp[100009];
string s;
typedef unsigned long long ull;
struct RollingHash{
  typedef unsigned long long ull;
  string S;
  ull B;
  int len;
  vector<ull> hash,p;
  RollingHash(){}
  RollingHash(string S_,ull B_=1000000007LL):
    S(S_),B(B_),len(S.length()),hash(len+1),p(len+1){
    hash[0]=0;p[0]=1;
    for(int i=0;i<len;i++){
      hash[i+1]=hash[i]*B+S[i];
      p[i+1]=p[i]*B;
    }
  }
  //S[l,r)
  ull find(int l,int r){
    return hash[r]-hash[l]*p[r-l];
  }
};

signed main(){
  vector<P>v;
  r(i,200009)r(j,27)trie[i][j]=-1;
  cin>>n;
  string t[n];
  r(i,n){
    cin>>s;
    if(s.size()<=500){
        int idx=0;
        r(j,s.size()){
            int p=s[j]-'a';
            if(trie[idx][p]==-1) trie[idx][p]=++c;
            idx=trie[idx][p];
        }
        trie[idx][26]=1;
    }
    else{
        RollingHash R(s);
        v.push_back(P(s.size(),R.find(0,s.size())));
    }
  }
  cin>>s;
  RollingHash R(s);
  dp[0]=1;
  r(i,s.size()){
    int idx=0,sum=0,j=i;
    while(trie[idx][s[j]-'a']!=-1 && j!=s.size()){
      idx=trie[idx][s[j]-'a'];
      if(trie[idx][26]==1)dp[j+1]+=dp[i];
      j++;
      dp[j]%=1000000007;
    }
    r(j,v.size()){
        int len=v[j].first;
        if(len+i>s.size())continue;
        if(R.find(i,i+len)==v[j].second){
            dp[i+len]+=dp[i];
            dp[i+len]%=1000000007;
        }
    }
  }
  cout<<dp[s.size()]<<endl;
}

### Prompt

Please formulate a Cpp solution to the following problem:

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 r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,unsigned long long>P;

int trie[200009][27],n,c,dp[100009];
string s;
typedef unsigned long long ull;
struct RollingHash{
  typedef unsigned long long ull;
  string S;
  ull B;
  int len;
  vector<ull> hash,p;
  RollingHash(){}
  RollingHash(string S_,ull B_=1000000007LL):
    S(S_),B(B_),len(S.length()),hash(len+1),p(len+1){
    hash[0]=0;p[0]=1;
    for(int i=0;i<len;i++){
      hash[i+1]=hash[i]*B+S[i];
      p[i+1]=p[i]*B;
    }
  }
  //S[l,r)
  ull find(int l,int r){
    return hash[r]-hash[l]*p[r-l];
  }
};

signed main(){
  vector<P>v;
  r(i,200009)r(j,27)trie[i][j]=-1;
  cin>>n;
  string t[n];
  r(i,n){
    cin>>s;
    if(s.size()<=500){
        int idx=0;
        r(j,s.size()){
            int p=s[j]-'a';
            if(trie[idx][p]==-1) trie[idx][p]=++c;
            idx=trie[idx][p];
        }
        trie[idx][26]=1;
    }
    else{
        RollingHash R(s);
        v.push_back(P(s.size(),R.find(0,s.size())));
    }
  }
  cin>>s;
  RollingHash R(s);
  dp[0]=1;
  r(i,s.size()){
    int idx=0,sum=0,j=i;
    while(trie[idx][s[j]-'a']!=-1 && j!=s.size()){
      idx=trie[idx][s[j]-'a'];
      if(trie[idx][26]==1)dp[j+1]+=dp[i];
      j++;
      dp[j]%=1000000007;
    }
    r(j,v.size()){
        int len=v[j].first;
        if(len+i>s.size())continue;
        if(R.find(i,i+len)==v[j].second){
            dp[i+len]+=dp[i];
            dp[i+len]%=1000000007;
        }
    }
  }
  cout<<dp[s.size()]<<endl;
}

```