#include<iostream>
#include<vector>
#include<set>
#include<map>
using namespace std;
int n;
string s[1<<17];
set<unsigned long>S[700];
map<int,int>M;
vector<unsigned long>h,make;
vector<int>le;
string t;
long dp[1<<17],mod=1e9+7;
int main()
{
	cin>>n;
	int sz=0;
	for(int i=0;i<n;i++)
	{
		cin>>s[i];
		int l=s[i].size();
		if(M.find(l)==M.end())
		{
			M[l]=sz++;
			le.push_back(l);
			h.push_back(0);
			unsigned long now=1;
			for(int j=0;j<l;j++)
			{
				now=now*mod;
			}
			make.push_back(now);
		}
		unsigned long tmp=0;
		for(int j=0;j<l;j++)tmp=tmp*mod+s[i][j];
		S[M[l]].insert(tmp);
	}
	cin>>t;
	dp[0]=1;
	for(int i=0;i<t.size();i++)
	{
		for(int j=0;j<sz;j++)
		{
			h[j]=h[j]*mod+t[i];
			if(i>=le[j])h[j]-=t[i-le[j]]*make[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

Create a solution in cpp for 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<iostream>
#include<vector>
#include<set>
#include<map>
using namespace std;
int n;
string s[1<<17];
set<unsigned long>S[700];
map<int,int>M;
vector<unsigned long>h,make;
vector<int>le;
string t;
long dp[1<<17],mod=1e9+7;
int main()
{
	cin>>n;
	int sz=0;
	for(int i=0;i<n;i++)
	{
		cin>>s[i];
		int l=s[i].size();
		if(M.find(l)==M.end())
		{
			M[l]=sz++;
			le.push_back(l);
			h.push_back(0);
			unsigned long now=1;
			for(int j=0;j<l;j++)
			{
				now=now*mod;
			}
			make.push_back(now);
		}
		unsigned long tmp=0;
		for(int j=0;j<l;j++)tmp=tmp*mod+s[i][j];
		S[M[l]].insert(tmp);
	}
	cin>>t;
	dp[0]=1;
	for(int i=0;i<t.size();i++)
	{
		for(int j=0;j<sz;j++)
		{
			h[j]=h[j]*mod+t[i];
			if(i>=le[j])h[j]-=t[i-le[j]]*make[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;
}

```