
#include <iostream>
#include <string>
#include <vector>
#define llint long long
#define ulint unsigned long long
#define mod 1000000007

using namespace std;

struct node{
  int num;
  int next[26];
  node(){
    num = 0;
    for(int i = 0; i < 26; i++) next[i] = -1;
  }
};

int n;
string s, t;
int R = 430;
vector<string> vec;
vector<node> trie;
ulint beki[200005];
ulint shash[200005], thash[200005];
llint dp[100005];

ulint getHash(string &s)
{
  ulint ret = 0;
  for(int i = 0; i < s.size(); i++) ret = ret * mod + s[i];
  return ret;
}

int main(void)
{
  cin >> n;

  beki[0] = 1;
  for(int i = 1; i < 200005; i++) beki[i] = beki[i-1] * mod;

  trie.push_back(node());
  for(int i = 1; i <= n; i++){
    cin >> s;
    if(s.size() >= R){
      vec.push_back(s);
      shash[vec.size()-1] = getHash(s);
    }
    else{
      int p = 0;
      for(int j = 0; j < s.size(); j++){
        if(trie[p].next[s[j]-'a'] == -1){
          trie.push_back(node());
          trie[p].next[s[j]-'a'] = trie.size()-1;
        }
        p = trie[p].next[s[j]-'a'];
      }
      trie[p].num++;
    }
  }

  cin >> t;
  int m = t.size();
  t = "#" + t;
  thash[0] = t[0];
  for(int i = 1; i <= m; i++){
    thash[i] = thash[i-1] * mod + t[i];
  }

  dp[0] = 1;
  for(int i = 0; i < m; i++){
    int p = 0;
    for(int j = 1; j < R; j++){
      if(i+j > m) break;
      p = trie[p].next[t[i+j]-'a'];
      if(p == -1) break;
      if(trie[p].num) dp[i+j] += dp[i], dp[i+j] %= mod;
    }
    for(int j = 0; j < vec.size(); j++){
      int len = vec[j].size(), l = i+1, r = i+len;
      if(r > m) continue;
      if(thash[r] - thash[l-1] * beki[r-l+1] == shash[j]) dp[r] += dp[i], dp[r] %= mod;
    }
  }
  cout << dp[m] << endl;

  return 0;
}


### Prompt

Your challenge is to write 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 <iostream>
#include <string>
#include <vector>
#define llint long long
#define ulint unsigned long long
#define mod 1000000007

using namespace std;

struct node{
  int num;
  int next[26];
  node(){
    num = 0;
    for(int i = 0; i < 26; i++) next[i] = -1;
  }
};

int n;
string s, t;
int R = 430;
vector<string> vec;
vector<node> trie;
ulint beki[200005];
ulint shash[200005], thash[200005];
llint dp[100005];

ulint getHash(string &s)
{
  ulint ret = 0;
  for(int i = 0; i < s.size(); i++) ret = ret * mod + s[i];
  return ret;
}

int main(void)
{
  cin >> n;

  beki[0] = 1;
  for(int i = 1; i < 200005; i++) beki[i] = beki[i-1] * mod;

  trie.push_back(node());
  for(int i = 1; i <= n; i++){
    cin >> s;
    if(s.size() >= R){
      vec.push_back(s);
      shash[vec.size()-1] = getHash(s);
    }
    else{
      int p = 0;
      for(int j = 0; j < s.size(); j++){
        if(trie[p].next[s[j]-'a'] == -1){
          trie.push_back(node());
          trie[p].next[s[j]-'a'] = trie.size()-1;
        }
        p = trie[p].next[s[j]-'a'];
      }
      trie[p].num++;
    }
  }

  cin >> t;
  int m = t.size();
  t = "#" + t;
  thash[0] = t[0];
  for(int i = 1; i <= m; i++){
    thash[i] = thash[i-1] * mod + t[i];
  }

  dp[0] = 1;
  for(int i = 0; i < m; i++){
    int p = 0;
    for(int j = 1; j < R; j++){
      if(i+j > m) break;
      p = trie[p].next[t[i+j]-'a'];
      if(p == -1) break;
      if(trie[p].num) dp[i+j] += dp[i], dp[i+j] %= mod;
    }
    for(int j = 0; j < vec.size(); j++){
      int len = vec[j].size(), l = i+1, r = i+len;
      if(r > m) continue;
      if(thash[r] - thash[l-1] * beki[r-l+1] == shash[j]) dp[r] += dp[i], dp[r] %= mod;
    }
  }
  cout << dp[m] << endl;

  return 0;
}


```