#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <math.h>
#include <deque>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

const int N=100001;
constexpr ll mod=1e9+7;

int dp[N];
ull m;
vector<ull> g[N];
ull po[N],hs[N];

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int q; cin >> q;
	string s; 
	while(q--){
		cin >> s;
		m=0;
		for(char c:s){
			m=m*911+c;
		}
		g[s.size()].push_back(m);
	}
	cin >> s;po[0]=1;
	for(int i=0;i<s.size();i++){
		po[i+1]=911*po[i];
		hs[i+1]=911*hs[i]+s[i];
	}
	vector<int> v;
	for(int i=1;i<=s.size();i++){
		if(g[i].size()){
			v.push_back(i);
			sort(g[i].begin(), g[i].end());
		}
	}
	dp[0]=1;
	for(int i=1;i<=s.size();i++){
		for(int j:v){
			if(j>i)continue;
			int l=0,r=g[j].size();
			ull f=hs[i]-hs[i-j]*po[j];
			while(r-l>1){
				int mi=(l+r)/2;
				if(g[j][mi]<=f)l=mi;
				else r=mi;
			}
			if(g[j][l]==f){
				dp[i]+=dp[i-j];
				if(dp[i]>=mod)dp[i]-=mod;
			}
		}
	}
	printf("%d\n",dp[s.size()]);
}

### Prompt

Construct a cpp code solution to the problem outlined:

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 <algorithm>
#include <set>
#include <map>
#include <math.h>
#include <deque>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

const int N=100001;
constexpr ll mod=1e9+7;

int dp[N];
ull m;
vector<ull> g[N];
ull po[N],hs[N];

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int q; cin >> q;
	string s; 
	while(q--){
		cin >> s;
		m=0;
		for(char c:s){
			m=m*911+c;
		}
		g[s.size()].push_back(m);
	}
	cin >> s;po[0]=1;
	for(int i=0;i<s.size();i++){
		po[i+1]=911*po[i];
		hs[i+1]=911*hs[i]+s[i];
	}
	vector<int> v;
	for(int i=1;i<=s.size();i++){
		if(g[i].size()){
			v.push_back(i);
			sort(g[i].begin(), g[i].end());
		}
	}
	dp[0]=1;
	for(int i=1;i<=s.size();i++){
		for(int j:v){
			if(j>i)continue;
			int l=0,r=g[j].size();
			ull f=hs[i]-hs[i-j]*po[j];
			while(r-l>1){
				int mi=(l+r)/2;
				if(g[j][mi]<=f)l=mi;
				else r=mi;
			}
			if(g[j][l]==f){
				dp[i]+=dp[i-j];
				if(dp[i]>=mod)dp[i]-=mod;
			}
		}
	}
	printf("%d\n",dp[s.size()]);
}

```