#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <tuple>
#include <cstring>
#include <queue>
using namespace std;
using ll = long long int;

const ll MOD = 1000000007;
const int SIZE = 26;

struct PMA {
  PMA* node[SIZE + 1];
  vector<int> matched;
  PMA() { memset(node, 0, sizeof(node)); }

  vector<int> unite(const vector<int> &a, const vector<int> &b) {
    vector<int> ret;
    set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(ret));
    return ret;
  }

  void build(vector<string> pattern) {
    PMA* root = this;
    root -> node[SIZE] = root;
    for(size_t i=0; i<pattern.size(); i++) {
      PMA* now = root;
      for(size_t j=0; j<pattern[i].size(); j++) {
        int c = pattern[i][j] - 'a';
        if(!now -> node[c]) {
          now -> node[c] = new PMA;
        }
        now = now -> node[c];
      }
      now -> matched.push_back(i);
    }

    queue<PMA*> que;
    for(int i=0; i<SIZE; i++) {
      if(!root -> node[i]) root -> node[i] = root;
      else {
        root -> node[i] -> node[SIZE] = root;
        que.push(root -> node[i]);
      }
    }

    while(que.size()) {
      PMA* now = que.front(); que.pop();
      for(int i=0; i<SIZE; i++) {
        if(now -> node[i]) {
          PMA* nxt = now -> node[SIZE];
          while(!nxt -> node[i]) nxt = nxt -> node[SIZE];

          now->node[i]->node[SIZE] = nxt->node[i];
          now->node[i]->matched=unite(now->node[i]->matched, nxt->node[i]->matched);
          que.push(now->node[i]);
        }
      }
    }
  }

  ll solve(const string s, vector<string> pattern) {
    PMA* pma = this;

    int N = s.length();
    vector<ll> dp(N+1);
    dp[0] = 1;
    for(size_t i=0; i<s.length(); i++) {
      int c = s[i] - 'a';
      while(!pma -> node[c]) pma = pma -> node[SIZE];

      pma = pma -> node[c];
      for(size_t j=0; j<pma->matched.size(); j++) {
        int r = i+1, l=r-pattern[ pma->matched[j] ].length();
        (dp[r] += dp[l]) %= MOD;
      }
    }

    return dp[N];
  }
};

int main() {
  int N; cin >> N;
  vector<string> pats(N);
  for(int i=0; i<N; i++) {
    cin >> pats[i];
  }

  string text; cin >> text;
  PMA pma;
  pma.build(pats);

  cout << pma.solve(text, pats) << endl;
  return 0;
}

### Prompt

Generate 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 <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <tuple>
#include <cstring>
#include <queue>
using namespace std;
using ll = long long int;

const ll MOD = 1000000007;
const int SIZE = 26;

struct PMA {
  PMA* node[SIZE + 1];
  vector<int> matched;
  PMA() { memset(node, 0, sizeof(node)); }

  vector<int> unite(const vector<int> &a, const vector<int> &b) {
    vector<int> ret;
    set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(ret));
    return ret;
  }

  void build(vector<string> pattern) {
    PMA* root = this;
    root -> node[SIZE] = root;
    for(size_t i=0; i<pattern.size(); i++) {
      PMA* now = root;
      for(size_t j=0; j<pattern[i].size(); j++) {
        int c = pattern[i][j] - 'a';
        if(!now -> node[c]) {
          now -> node[c] = new PMA;
        }
        now = now -> node[c];
      }
      now -> matched.push_back(i);
    }

    queue<PMA*> que;
    for(int i=0; i<SIZE; i++) {
      if(!root -> node[i]) root -> node[i] = root;
      else {
        root -> node[i] -> node[SIZE] = root;
        que.push(root -> node[i]);
      }
    }

    while(que.size()) {
      PMA* now = que.front(); que.pop();
      for(int i=0; i<SIZE; i++) {
        if(now -> node[i]) {
          PMA* nxt = now -> node[SIZE];
          while(!nxt -> node[i]) nxt = nxt -> node[SIZE];

          now->node[i]->node[SIZE] = nxt->node[i];
          now->node[i]->matched=unite(now->node[i]->matched, nxt->node[i]->matched);
          que.push(now->node[i]);
        }
      }
    }
  }

  ll solve(const string s, vector<string> pattern) {
    PMA* pma = this;

    int N = s.length();
    vector<ll> dp(N+1);
    dp[0] = 1;
    for(size_t i=0; i<s.length(); i++) {
      int c = s[i] - 'a';
      while(!pma -> node[c]) pma = pma -> node[SIZE];

      pma = pma -> node[c];
      for(size_t j=0; j<pma->matched.size(); j++) {
        int r = i+1, l=r-pattern[ pma->matched[j] ].length();
        (dp[r] += dp[l]) %= MOD;
      }
    }

    return dp[N];
  }
};

int main() {
  int N; cin >> N;
  vector<string> pats(N);
  for(int i=0; i<N; i++) {
    cin >> pats[i];
  }

  string text; cin >> text;
  PMA pma;
  pma.build(pats);

  cout << pma.solve(text, pats) << endl;
  return 0;
}

```