#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <unordered_set>

using namespace std;

typedef long long LL;

const int P0 = 23;
const int P1 = 67;
const int MOD0 = 998244353;
const int MOD1 = 1000000007;

typedef pair<int , int> P;

#define mkp(a , b) make_pair(a , b)
#define ft first
#define sd second

inline P operator + (P p , P q){return mkp((p.ft + q.ft) % MOD0 , (p.sd + q.sd) % MOD1);}
inline P operator - (P p , P q){return mkp((p.ft - q.ft + MOD0) % MOD0 , (p.sd - q.sd + MOD1) % MOD1);}
inline P operator * (P p , P q){return mkp(1ll * p.ft * q.ft % MOD0 ,  1ll * p.sd * q.sd % MOD1);}

inline P &operator +=(P &p , P q){return p = p + q;}
inline P &operator -=(P &p , P q){return p = p - q;}
inline P &operator *=(P &p , P q){return p = p * q;}

const int N = 100005;
const int L = 100005;

unordered_set<LL> exist;

P hash_value[L] , inv[L] , invp;
char s[L] , t[L];
int len[N];
int f[L];
int n , l;

inline int quick_power(int x , int y , int mod)
{
	int ret = 1;
	for (;y;y >>= 1 , x = 1ll * x * x % mod) if (y & 1) ret = 1ll * ret * x % mod;
	return ret;
}

inline void add(int &x , int y){x = x + y >= MOD1 ? x + y - MOD1 : x + y;}

int main()
{
	//freopen("b.in" , "r" , stdin) , freopen("b.out" , "w" , stdout);
	scanf("%d" , &n);
	for (int i = 1 , l_;i <= n;++ i)
	{
		scanf("%s" , s + 1) , l_ = strlen(s + 1) , len[i] = l_;
		P base = mkp(1 , 1) , cur = mkp(0 , 0);
		for (int j = 1;j <= l_;++ j)
		{
			cur += base * mkp(s[j] - 'a' + 1 , s[j] - 'a' + 1);
			base *= mkp(P0 , P1);
		}
		exist.insert(cur.ft * 1000000000ll + cur.sd);
	}
	sort(len + 1 , len + 1 + n) , n = unique(len + 1 , len + 1 + n) - (len + 1);
	scanf("%s" , t + 1) , l = strlen(t + 1);
	inv[0] = mkp(1 , 1) , invp = mkp(quick_power(P0 , MOD0 - 2 , MOD0) , quick_power(P1 , MOD1 - 2 , MOD1));
	P base = mkp(1 , 1);
	f[0] = 1;
	for (int i = 1;i <= l;++ i)
	{
		inv[i] = inv[i - 1] * invp;
		hash_value[i] = hash_value[i - 1] + base * mkp(t[i] - 'a' + 1 , t[i] - 'a' + 1);
		for (int j = 1;j <= n && len[j] <= i;++ j)
		{
			P range_hash = (hash_value[i] - hash_value[i - len[j]]) * inv[i - len[j]];
			if (exist.count(range_hash.ft * 1000000000ll + range_hash.sd)) add(f[i] , f[i - len[j]]);
		}
		base *= mkp(P0 , P1);
	}
	printf("%d\n" , f[l]);
	//fclose(stdin) , fclose(stdout);
	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 <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <unordered_set>

using namespace std;

typedef long long LL;

const int P0 = 23;
const int P1 = 67;
const int MOD0 = 998244353;
const int MOD1 = 1000000007;

typedef pair<int , int> P;

#define mkp(a , b) make_pair(a , b)
#define ft first
#define sd second

inline P operator + (P p , P q){return mkp((p.ft + q.ft) % MOD0 , (p.sd + q.sd) % MOD1);}
inline P operator - (P p , P q){return mkp((p.ft - q.ft + MOD0) % MOD0 , (p.sd - q.sd + MOD1) % MOD1);}
inline P operator * (P p , P q){return mkp(1ll * p.ft * q.ft % MOD0 ,  1ll * p.sd * q.sd % MOD1);}

inline P &operator +=(P &p , P q){return p = p + q;}
inline P &operator -=(P &p , P q){return p = p - q;}
inline P &operator *=(P &p , P q){return p = p * q;}

const int N = 100005;
const int L = 100005;

unordered_set<LL> exist;

P hash_value[L] , inv[L] , invp;
char s[L] , t[L];
int len[N];
int f[L];
int n , l;

inline int quick_power(int x , int y , int mod)
{
	int ret = 1;
	for (;y;y >>= 1 , x = 1ll * x * x % mod) if (y & 1) ret = 1ll * ret * x % mod;
	return ret;
}

inline void add(int &x , int y){x = x + y >= MOD1 ? x + y - MOD1 : x + y;}

int main()
{
	//freopen("b.in" , "r" , stdin) , freopen("b.out" , "w" , stdout);
	scanf("%d" , &n);
	for (int i = 1 , l_;i <= n;++ i)
	{
		scanf("%s" , s + 1) , l_ = strlen(s + 1) , len[i] = l_;
		P base = mkp(1 , 1) , cur = mkp(0 , 0);
		for (int j = 1;j <= l_;++ j)
		{
			cur += base * mkp(s[j] - 'a' + 1 , s[j] - 'a' + 1);
			base *= mkp(P0 , P1);
		}
		exist.insert(cur.ft * 1000000000ll + cur.sd);
	}
	sort(len + 1 , len + 1 + n) , n = unique(len + 1 , len + 1 + n) - (len + 1);
	scanf("%s" , t + 1) , l = strlen(t + 1);
	inv[0] = mkp(1 , 1) , invp = mkp(quick_power(P0 , MOD0 - 2 , MOD0) , quick_power(P1 , MOD1 - 2 , MOD1));
	P base = mkp(1 , 1);
	f[0] = 1;
	for (int i = 1;i <= l;++ i)
	{
		inv[i] = inv[i - 1] * invp;
		hash_value[i] = hash_value[i - 1] + base * mkp(t[i] - 'a' + 1 , t[i] - 'a' + 1);
		for (int j = 1;j <= n && len[j] <= i;++ j)
		{
			P range_hash = (hash_value[i] - hash_value[i - len[j]]) * inv[i - len[j]];
			if (exist.count(range_hash.ft * 1000000000ll + range_hash.sd)) add(f[i] , f[i - len[j]]);
		}
		base *= mkp(P0 , P1);
	}
	printf("%d\n" , f[l]);
	//fclose(stdin) , fclose(stdout);
	return 0;
}

```