#include<bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

struct trie{
	int to[26];
	int val;
	trie(){
		val=0;
	}
};

int size=1;
trie t[1<<19];

vector<int> make(const string& str){
	int n=str.size();
	vector<int> ret(n+1);
	ret[0]=-1;
	int j=-1;
	for(int i=0;i<n;i++){
		while(j>=0 && str[i]!=str[j]){
			j=ret[j];
		}
		ret[i+1]=++j;
	}
	return ret;
}

int now=0;
vector<int> ret[201];
int moveto[201];
int koko[201];

void kmp(const string& str,const string& word){
	vector<int> table=make(word);
	int m=0,i=0,n=str.size();
	while(m+i<n){
		if(word[i]==str[m+i]){
			if(++i==(int)(word.size())){
				ret[now].push_back(m);
				m=m+i-table[i];
				i=table[i];
			}
		}else{
			m=m+i-table[i];
			if(i>0)i=table[i];
		}
	}
}

void pushTrie(string str){
	int node=0;
	for(int i=0;i<(int)str.size();i++){
		int b=(str[i]-'a');
		if(t[node].to[b]==0){
			t[node].to[b]=size++;
		}
		node=t[node].to[b];
	}
	t[node].val++;
}

string str;
int n;
ll dp[100001];

void sendValue(int f,ll val){
	int node=0;
	for(int i=0;i<=1000;i++){
		if(i+f>=n)return;
		int b=(str[i+f]-'a');
		if(t[node].to[b]==0)return;
		node=t[node].to[b];
		if(t[node].val>0){
			dp[i+f+1]+=val;
			if(dp[i+f+1]>=MOD)dp[i+f+1]%=MOD;
		}
	}
	return;
}



string s[100001];
int als=0;

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		cin >> s[i];
	}
	cin >> str;

	for(int i=0;i<n;i++){
		if(s[i].size()<=1000){
			pushTrie(s[i]);
		}else{
			kmp(str,s[i]);
			moveto[now]=s[i].size();
			now++;
		}
	}
	n=str.size();
	dp[0]=1;
	for(int i=0;i<n;i++){
		sendValue(i,dp[i]);
		for(int j=0;j<now;j++){
			int k=koko[j];
			if(k<ret[j].size() && ret[j][k]==i){
				dp[i+moveto[j]]+=dp[i];
				if(dp[i+moveto[j]]>=MOD){
					dp[i+moveto[j]]%=MOD;
				}
				koko[j]++;
			}
		}
	}
	printf("%lld\n",dp[n]);
	return 0;
}
### 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 MOD 1000000007LL
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

struct trie{
	int to[26];
	int val;
	trie(){
		val=0;
	}
};

int size=1;
trie t[1<<19];

vector<int> make(const string& str){
	int n=str.size();
	vector<int> ret(n+1);
	ret[0]=-1;
	int j=-1;
	for(int i=0;i<n;i++){
		while(j>=0 && str[i]!=str[j]){
			j=ret[j];
		}
		ret[i+1]=++j;
	}
	return ret;
}

int now=0;
vector<int> ret[201];
int moveto[201];
int koko[201];

void kmp(const string& str,const string& word){
	vector<int> table=make(word);
	int m=0,i=0,n=str.size();
	while(m+i<n){
		if(word[i]==str[m+i]){
			if(++i==(int)(word.size())){
				ret[now].push_back(m);
				m=m+i-table[i];
				i=table[i];
			}
		}else{
			m=m+i-table[i];
			if(i>0)i=table[i];
		}
	}
}

void pushTrie(string str){
	int node=0;
	for(int i=0;i<(int)str.size();i++){
		int b=(str[i]-'a');
		if(t[node].to[b]==0){
			t[node].to[b]=size++;
		}
		node=t[node].to[b];
	}
	t[node].val++;
}

string str;
int n;
ll dp[100001];

void sendValue(int f,ll val){
	int node=0;
	for(int i=0;i<=1000;i++){
		if(i+f>=n)return;
		int b=(str[i+f]-'a');
		if(t[node].to[b]==0)return;
		node=t[node].to[b];
		if(t[node].val>0){
			dp[i+f+1]+=val;
			if(dp[i+f+1]>=MOD)dp[i+f+1]%=MOD;
		}
	}
	return;
}



string s[100001];
int als=0;

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		cin >> s[i];
	}
	cin >> str;

	for(int i=0;i<n;i++){
		if(s[i].size()<=1000){
			pushTrie(s[i]);
		}else{
			kmp(str,s[i]);
			moveto[now]=s[i].size();
			now++;
		}
	}
	n=str.size();
	dp[0]=1;
	for(int i=0;i<n;i++){
		sendValue(i,dp[i]);
		for(int j=0;j<now;j++){
			int k=koko[j];
			if(k<ret[j].size() && ret[j][k]==i){
				dp[i+moveto[j]]+=dp[i];
				if(dp[i+moveto[j]]>=MOD){
					dp[i+moveto[j]]%=MOD;
				}
				koko[j]++;
			}
		}
	}
	printf("%lld\n",dp[n]);
	return 0;
}
```