#include<bits/stdc++.h>
using namespace std;
using Int = long long;



struct RollingHash{
  typedef unsigned long long ull;
  string S;
  ull B;
  Int len;
  vector<ull> hash,p;
  RollingHash(){}
  RollingHash(string S_,ull B_ = 1e9+7):
    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;
    }
  }

  ull find(Int l,Int r){
    return hash[r] - hash[l] * p[r-l];
  }
};


signed main(){  
  cin.tie(0);
  ios::sync_with_stdio(0);
  Int n;
  cin>>n;
  vector<string> s(n);
  for(Int i=0;i<n;i++) cin>>s[i];
  
  string t;
  cin>>t;
  
  vector<RollingHash> rhs;
  for(Int i=0;i<n;i++) rhs.push_back(RollingHash(s[i]));
  using ull=RollingHash::ull;
  vector< vector<Int> > l(26);
  vector< vector<ull> > v(26);
  for(Int i=0;i<n;i++){
    l[s[i][0]-'a'].push_back(s[i].size());
    v[s[i][0]-'a'].push_back(rhs[i].find(0,s[i].size()));
  }
  
  RollingHash rht(t);
  vector<Int> dp(t.size()+1,0);
  dp[0]=1;
  const Int MOD=1e9+7;
  for(Int i=0;i<(Int)t.size();i++){
    if(!dp[i]) continue;
    for(Int j=0;j<(Int)l[t[i]-'a'].size();j++){
      if(i+l[t[i]-'a'][j]>(Int)t.size()) continue;
      if(rht.find(i,i+l[t[i]-'a'][j])==v[t[i]-'a'][j]){
	dp[i+l[t[i]-'a'][j]]+=dp[i];
	dp[i+l[t[i]-'a'][j]]%=MOD;
      }
    }
  }
  cout<<dp.back()<<endl;
  return 0;
}


### Prompt

In CPP, your task is to solve 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>
using namespace std;
using Int = long long;



struct RollingHash{
  typedef unsigned long long ull;
  string S;
  ull B;
  Int len;
  vector<ull> hash,p;
  RollingHash(){}
  RollingHash(string S_,ull B_ = 1e9+7):
    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;
    }
  }

  ull find(Int l,Int r){
    return hash[r] - hash[l] * p[r-l];
  }
};


signed main(){  
  cin.tie(0);
  ios::sync_with_stdio(0);
  Int n;
  cin>>n;
  vector<string> s(n);
  for(Int i=0;i<n;i++) cin>>s[i];
  
  string t;
  cin>>t;
  
  vector<RollingHash> rhs;
  for(Int i=0;i<n;i++) rhs.push_back(RollingHash(s[i]));
  using ull=RollingHash::ull;
  vector< vector<Int> > l(26);
  vector< vector<ull> > v(26);
  for(Int i=0;i<n;i++){
    l[s[i][0]-'a'].push_back(s[i].size());
    v[s[i][0]-'a'].push_back(rhs[i].find(0,s[i].size()));
  }
  
  RollingHash rht(t);
  vector<Int> dp(t.size()+1,0);
  dp[0]=1;
  const Int MOD=1e9+7;
  for(Int i=0;i<(Int)t.size();i++){
    if(!dp[i]) continue;
    for(Int j=0;j<(Int)l[t[i]-'a'].size();j++){
      if(i+l[t[i]-'a'][j]>(Int)t.size()) continue;
      if(rht.find(i,i+l[t[i]-'a'][j])==v[t[i]-'a'][j]){
	dp[i+l[t[i]-'a'][j]]+=dp[i];
	dp[i+l[t[i]-'a'][j]]%=MOD;
      }
    }
  }
  cout<<dp.back()<<endl;
  return 0;
}


```