#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll in()
{
    ll re=0,f=1;char x=getchar();
    while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
    while(x>='0'&&x<='9')re=re*10+x-48,x=getchar();
    return re*f;
}
void out(ll x)
{
    if(x<0)putchar('-'),x=-x;
    if(!x){putchar('0');return;}
    char z[21],ct=0;
    while(x){z[++ct]=x%10+48,x/=10;}
    while(ct){putchar(z[ct]);--ct;}
}
int n;
char ss[500000];
int s[100010],pt;
int len[100010],tlen;
char t[100010];
int ptr=1;
const ll mod=1e9+7;
struct node{
    int ch[26],fa;
    char v;
    vector<int>cnt;
}nd[200010];
void ins(int l,int len)
{
    int cur=1;
    for(int i=l;i<l+len;++i)
    {
        char c=ss[i];
        if(!nd[cur].ch[c-'a'])
        {
            nd[cur].ch[c-'a']=++ptr;
            nd[ptr].fa=cur;
            nd[ptr].v=c;
        }
        cur=nd[cur].ch[c-'a'];
    }
    nd[cur].cnt.push_back(len);
}
int fail[200010];
void bfs()
{
    queue<int>q;
    fail[1]=1;
    for(int i=0;i<26;++i)
    if(nd[1].ch[i])
    {
        fail[nd[1].ch[i]]=1;
        q.push(nd[1].ch[i]);
    }
    else nd[1].ch[i]=1;
    while(!q.empty())
    {
        int h=q.front();q.pop();
        for(int i=0;i<26;++i)
        if(nd[h].ch[i])
        {
            fail[nd[h].ch[i]]=nd[fail[h]].ch[i];
            q.push(nd[h].ch[i]);
        }
        else nd[h].ch[i]=nd[fail[h]].ch[i];
    }
}
ll dp[200010];
int main()
{
    scanf("%d\n",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%s",ss+pt);
        s[i]=pt;
        len[i]=strlen(ss+pt);
        pt=pt+len[i]+1;
    }
    for(int i=1;i<=n;++i)
        ins(s[i],len[i]);
    bfs();
    scanf("%s",t+1);
    tlen=strlen(t+1);
    dp[0]=1;
    int cur=1;
    for(int i=1;i<=tlen;++i)
    {
        cur=nd[cur].ch[t[i]-'a'];
        int now=cur;
        while(now>1)
        {
            vector<int>&v=nd[now].cnt;
            for(int j=0;j<v.size();++j)
                dp[i]=(dp[i]+dp[i-v[j]])%mod;
            now=fail[now];
        }
    }
    cout<<dp[tlen]<<'\n';
}

### Prompt

Generate 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>
using namespace std;
typedef long long ll;
ll in()
{
    ll re=0,f=1;char x=getchar();
    while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
    while(x>='0'&&x<='9')re=re*10+x-48,x=getchar();
    return re*f;
}
void out(ll x)
{
    if(x<0)putchar('-'),x=-x;
    if(!x){putchar('0');return;}
    char z[21],ct=0;
    while(x){z[++ct]=x%10+48,x/=10;}
    while(ct){putchar(z[ct]);--ct;}
}
int n;
char ss[500000];
int s[100010],pt;
int len[100010],tlen;
char t[100010];
int ptr=1;
const ll mod=1e9+7;
struct node{
    int ch[26],fa;
    char v;
    vector<int>cnt;
}nd[200010];
void ins(int l,int len)
{
    int cur=1;
    for(int i=l;i<l+len;++i)
    {
        char c=ss[i];
        if(!nd[cur].ch[c-'a'])
        {
            nd[cur].ch[c-'a']=++ptr;
            nd[ptr].fa=cur;
            nd[ptr].v=c;
        }
        cur=nd[cur].ch[c-'a'];
    }
    nd[cur].cnt.push_back(len);
}
int fail[200010];
void bfs()
{
    queue<int>q;
    fail[1]=1;
    for(int i=0;i<26;++i)
    if(nd[1].ch[i])
    {
        fail[nd[1].ch[i]]=1;
        q.push(nd[1].ch[i]);
    }
    else nd[1].ch[i]=1;
    while(!q.empty())
    {
        int h=q.front();q.pop();
        for(int i=0;i<26;++i)
        if(nd[h].ch[i])
        {
            fail[nd[h].ch[i]]=nd[fail[h]].ch[i];
            q.push(nd[h].ch[i]);
        }
        else nd[h].ch[i]=nd[fail[h]].ch[i];
    }
}
ll dp[200010];
int main()
{
    scanf("%d\n",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%s",ss+pt);
        s[i]=pt;
        len[i]=strlen(ss+pt);
        pt=pt+len[i]+1;
    }
    for(int i=1;i<=n;++i)
        ins(s[i],len[i]);
    bfs();
    scanf("%s",t+1);
    tlen=strlen(t+1);
    dp[0]=1;
    int cur=1;
    for(int i=1;i<=tlen;++i)
    {
        cur=nd[cur].ch[t[i]-'a'];
        int now=cur;
        while(now>1)
        {
            vector<int>&v=nd[now].cnt;
            for(int j=0;j<v.size();++j)
                dp[i]=(dp[i]+dp[i-v[j]])%mod;
            now=fail[now];
        }
    }
    cout<<dp[tlen]<<'\n';
}

```