#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define rep(i,n) for(int i=0; i<n; i++)
#define rep1(i,n) for(int i=1; i<n; i++)
#define all(a) (a).begin(),(a).end();

using uLL=unsigned long long;
map<int,int>M;
set<uLL>S[700];
int n;
string s[1<<17];
LL dp[1<<17],mod=1e9+7;
uLL gethash(string a)
{
  uLL B=mod;
  uLL now=0;
  for(int i=0;i<a.size();i++)now=now*B+a[i];
  return now;
}
vector<uLL>h(1);
vector<uLL>make(1);
vector<int>le(1);

int main(){
  cin>>n;
  int sz=0;
  for(int i=0;i<n;i++)
  {
    cin>>s[i];
    int l=s[i].length();
    int id;
    if(M[l]==0)
    {
      id=M[l]=++sz;
      uLL now=1;
      uLL B=mod;
      for(int j=0;j<l;j++)now=now*B;
      make.push_back(now);
      h.push_back(0);
      le.push_back(l);
    }
    else id=M[l];
    S[id].insert(gethash(s[i]));
  }
  string t;cin>>t;
  dp[0]=1;
  for(int i=0;i<t.size();i++)
  {
    for(int j=1;j<=sz;j++)
    {
      h[j]=h[j]*(uLL)mod+t[i];
      if(i>=le[j])h[j]=h[j]-make[j]*t[i-le[j]];
      if(i>=le[j]-1&&S[j].find(h[j])!=S[j].end())
      {
        dp[i+1]=(dp[i+1]+dp[i+1-le[j]])%mod;
      }
    }
  }
  cout<<dp[t.size()]<<endl;
}


### Prompt

Develop a solution in Cpp 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>
using namespace std;
using LL=long long;
#define rep(i,n) for(int i=0; i<n; i++)
#define rep1(i,n) for(int i=1; i<n; i++)
#define all(a) (a).begin(),(a).end();

using uLL=unsigned long long;
map<int,int>M;
set<uLL>S[700];
int n;
string s[1<<17];
LL dp[1<<17],mod=1e9+7;
uLL gethash(string a)
{
  uLL B=mod;
  uLL now=0;
  for(int i=0;i<a.size();i++)now=now*B+a[i];
  return now;
}
vector<uLL>h(1);
vector<uLL>make(1);
vector<int>le(1);

int main(){
  cin>>n;
  int sz=0;
  for(int i=0;i<n;i++)
  {
    cin>>s[i];
    int l=s[i].length();
    int id;
    if(M[l]==0)
    {
      id=M[l]=++sz;
      uLL now=1;
      uLL B=mod;
      for(int j=0;j<l;j++)now=now*B;
      make.push_back(now);
      h.push_back(0);
      le.push_back(l);
    }
    else id=M[l];
    S[id].insert(gethash(s[i]));
  }
  string t;cin>>t;
  dp[0]=1;
  for(int i=0;i<t.size();i++)
  {
    for(int j=1;j<=sz;j++)
    {
      h[j]=h[j]*(uLL)mod+t[i];
      if(i>=le[j])h[j]=h[j]-make[j]*t[i-le[j]];
      if(i>=le[j]-1&&S[j].find(h[j])!=S[j].end())
      {
        dp[i+1]=(dp[i+1]+dp[i+1-le[j]])%mod;
      }
    }
  }
  cout<<dp[t.size()]<<endl;
}


```