#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

template<int char_size>
struct TrieNode {
  std::vector<int> nxt;

  int exist;
  std::vector<int> accept;

  TrieNode():nxt(char_size+1, -1), exist(0) {}
};

template<int char_size, int margin>
struct Trie {
  using Node = TrieNode<char_size>;

  std::vector<Node> nodes;
  int root;

  Trie():root(0) { nodes.push_back(Node()); }

  virtual void direct_action(int node, int id) {node++;id++;}
  virtual void child_action(int node, int child, int id) {node++;child++;id++;}

  void update_direct(int node, int id) {
    nodes[node].accept.push_back(id);
    direct_action(node, id);
  }
  void update_child(int node, int child, int id) {
    ++nodes[node].exist;
    child_action(node, child, id);
  }
  void add(const std::string& str, int str_idx, int node_idx, int id) {
    if(str_idx == static_cast<int>(str.size())) {
      update_direct(node_idx, id);
    } else {
      const int c = str[str_idx]-margin;
      if(nodes[node_idx].nxt[c] == -1) {
	nodes[node_idx].nxt[c] = nodes.size();
	nodes.push_back(Node());
      }
      add(str, str_idx+1, nodes[node_idx].nxt[c], id);
      update_child(node_idx, nodes[node_idx].nxt[c], id);
    }
  }
  void add(const std::string& str, int id) {
    add(str, 0, 0, id);
  }
  void add(const std::string& str) {
    add(str, nodes[0].exist);
  }
  void query(const std::string& str, const std::function<void(int)>& f, int str_idx, int node_idx) {
    for(auto& idx : nodes[node_idx].accept) f(idx);
    if(str_idx == static_cast<int>(str.size())) {
      return;
    } else {
      const int c = str[str_idx]-margin;
      if(nodes[node_idx].nxt[c] == -1) return;
      query(str, f, str_idx+1, nodes[node_idx].nxt[c]);
    }
  }
  void query(const std::string& str, const std::function<void(int)>& f) {
    query(str, f, 0, 0);
  }
  int size() const {
    return nodes[0].exist;
  }
  int node_size() const {
    return nodes.size();
  }
  const Node& operator [](int k) const {
    return nodes[k];
  }
};

template<int char_size, int margin>
struct Aho_Corasick : Trie<char_size, margin> {
  using TRIE = Trie<char_size, margin>;
  static const int FAIL = char_size;
  std::vector<int> correct;

  Aho_Corasick() : TRIE(){}

  void build(bool heavy = true) {
    correct.resize(TRIE::nodes.size());
    for(int i = 0; i < TRIE::nodes.size(); ++i) {
      correct[i] = TRIE::nodes[i].accept.size();
    }

    std::queue<int> que;
    for(int i = 0; i <= char_size; ++i) {
      if(~TRIE::nodes[0].nxt[i]) {
	TRIE::nodes[TRIE::nodes[0].nxt[i]].nxt[FAIL] = 0;
	que.emplace(TRIE::nodes[0].nxt[i]);
      } else {
	TRIE::nodes[0].nxt[i] = 0;
      }
    }

    while(!que.empty()) {
      TrieNode<char_size>& now = TRIE::nodes[que.front()];
      correct[que.front()] += correct[now.nxt[FAIL]];
      que.pop();
      for(int i = 0; i < char_size; ++i) {
	if(now.nxt[i] == -1) continue;
	int fail = now.nxt[FAIL];
	while(TRIE::nodes[fail].nxt[i] == -1) fail = TRIE::nodes[fail].nxt[FAIL];
	TRIE::nodes[now.nxt[i]].nxt[FAIL] = TRIE::nodes[fail].nxt[i];
	if(heavy) {
	  auto& u = TRIE::nodes[now.nxt[i]].accept;
	  auto& v = TRIE::nodes[TRIE::nodes[fail].nxt[i]].accept;
	  std::vector<int> accept;
	  set_union(begin(u), end(u), begin(v), end(v), back_inserter(accept));
	  u = accept;
	}
	que.emplace(now.nxt[i]);
      }
    }
  }
  int match(const std::string& str, std::vector<int>& result, int now = 0) {
    result.assign(TRIE::size(), 0);
    int cnt = 0;
    for(auto& c : str) {
      while(TRIE::nodes[now].nxt[c-margin] == -1) now = TRIE::nodes[now].nxt[FAIL];
      now = TRIE::nodes[now].nxt[c-margin];
      cnt += correct[now];
      for(auto& v : TRIE::nodes[now].accept) ++result[v];
    }
    return cnt;
  }
  int move(const char& c, int& now) {
    int cnt = 0;
      while(TRIE::nodes[now].nxt[c-margin] == -1) now = TRIE::nodes[now].nxt[FAIL];
      now = TRIE::nodes[now].nxt[c-margin];
      cnt += correct[now];
      return cnt;
  }
};

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N;
  cin >> N;
  Aho_Corasick<26, 'a'> aho;
  vector<string> s(N);
  rep(i, N) {
    cin >> s[i];
    aho.add(s[i]);
  }
  aho.build();
  string t;
  cin >> t;
  int L = t.size();
  vint dp(L+1);
  dp[0] = 1;
  int now = aho.root;
  rep(i, L) {
    aho.move(t[i], now);
    //cout<<now<<endl;
    //cout << "T[0:"<<i<<"] "<<t.substr(0, i+1) << endl;
    for(int j : aho[now].accept) {
      //cout << j << " " << s[j] << endl;
      dp[i+1] += dp[i-s[j].size()+1];
      dp[i+1] %= mod;
    }
  }
  cout << dp[L] << endl;

  return 0;
}


### Prompt

Please create a solution in CPP 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>

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

template<int char_size>
struct TrieNode {
  std::vector<int> nxt;

  int exist;
  std::vector<int> accept;

  TrieNode():nxt(char_size+1, -1), exist(0) {}
};

template<int char_size, int margin>
struct Trie {
  using Node = TrieNode<char_size>;

  std::vector<Node> nodes;
  int root;

  Trie():root(0) { nodes.push_back(Node()); }

  virtual void direct_action(int node, int id) {node++;id++;}
  virtual void child_action(int node, int child, int id) {node++;child++;id++;}

  void update_direct(int node, int id) {
    nodes[node].accept.push_back(id);
    direct_action(node, id);
  }
  void update_child(int node, int child, int id) {
    ++nodes[node].exist;
    child_action(node, child, id);
  }
  void add(const std::string& str, int str_idx, int node_idx, int id) {
    if(str_idx == static_cast<int>(str.size())) {
      update_direct(node_idx, id);
    } else {
      const int c = str[str_idx]-margin;
      if(nodes[node_idx].nxt[c] == -1) {
	nodes[node_idx].nxt[c] = nodes.size();
	nodes.push_back(Node());
      }
      add(str, str_idx+1, nodes[node_idx].nxt[c], id);
      update_child(node_idx, nodes[node_idx].nxt[c], id);
    }
  }
  void add(const std::string& str, int id) {
    add(str, 0, 0, id);
  }
  void add(const std::string& str) {
    add(str, nodes[0].exist);
  }
  void query(const std::string& str, const std::function<void(int)>& f, int str_idx, int node_idx) {
    for(auto& idx : nodes[node_idx].accept) f(idx);
    if(str_idx == static_cast<int>(str.size())) {
      return;
    } else {
      const int c = str[str_idx]-margin;
      if(nodes[node_idx].nxt[c] == -1) return;
      query(str, f, str_idx+1, nodes[node_idx].nxt[c]);
    }
  }
  void query(const std::string& str, const std::function<void(int)>& f) {
    query(str, f, 0, 0);
  }
  int size() const {
    return nodes[0].exist;
  }
  int node_size() const {
    return nodes.size();
  }
  const Node& operator [](int k) const {
    return nodes[k];
  }
};

template<int char_size, int margin>
struct Aho_Corasick : Trie<char_size, margin> {
  using TRIE = Trie<char_size, margin>;
  static const int FAIL = char_size;
  std::vector<int> correct;

  Aho_Corasick() : TRIE(){}

  void build(bool heavy = true) {
    correct.resize(TRIE::nodes.size());
    for(int i = 0; i < TRIE::nodes.size(); ++i) {
      correct[i] = TRIE::nodes[i].accept.size();
    }

    std::queue<int> que;
    for(int i = 0; i <= char_size; ++i) {
      if(~TRIE::nodes[0].nxt[i]) {
	TRIE::nodes[TRIE::nodes[0].nxt[i]].nxt[FAIL] = 0;
	que.emplace(TRIE::nodes[0].nxt[i]);
      } else {
	TRIE::nodes[0].nxt[i] = 0;
      }
    }

    while(!que.empty()) {
      TrieNode<char_size>& now = TRIE::nodes[que.front()];
      correct[que.front()] += correct[now.nxt[FAIL]];
      que.pop();
      for(int i = 0; i < char_size; ++i) {
	if(now.nxt[i] == -1) continue;
	int fail = now.nxt[FAIL];
	while(TRIE::nodes[fail].nxt[i] == -1) fail = TRIE::nodes[fail].nxt[FAIL];
	TRIE::nodes[now.nxt[i]].nxt[FAIL] = TRIE::nodes[fail].nxt[i];
	if(heavy) {
	  auto& u = TRIE::nodes[now.nxt[i]].accept;
	  auto& v = TRIE::nodes[TRIE::nodes[fail].nxt[i]].accept;
	  std::vector<int> accept;
	  set_union(begin(u), end(u), begin(v), end(v), back_inserter(accept));
	  u = accept;
	}
	que.emplace(now.nxt[i]);
      }
    }
  }
  int match(const std::string& str, std::vector<int>& result, int now = 0) {
    result.assign(TRIE::size(), 0);
    int cnt = 0;
    for(auto& c : str) {
      while(TRIE::nodes[now].nxt[c-margin] == -1) now = TRIE::nodes[now].nxt[FAIL];
      now = TRIE::nodes[now].nxt[c-margin];
      cnt += correct[now];
      for(auto& v : TRIE::nodes[now].accept) ++result[v];
    }
    return cnt;
  }
  int move(const char& c, int& now) {
    int cnt = 0;
      while(TRIE::nodes[now].nxt[c-margin] == -1) now = TRIE::nodes[now].nxt[FAIL];
      now = TRIE::nodes[now].nxt[c-margin];
      cnt += correct[now];
      return cnt;
  }
};

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N;
  cin >> N;
  Aho_Corasick<26, 'a'> aho;
  vector<string> s(N);
  rep(i, N) {
    cin >> s[i];
    aho.add(s[i]);
  }
  aho.build();
  string t;
  cin >> t;
  int L = t.size();
  vint dp(L+1);
  dp[0] = 1;
  int now = aho.root;
  rep(i, L) {
    aho.move(t[i], now);
    //cout<<now<<endl;
    //cout << "T[0:"<<i<<"] "<<t.substr(0, i+1) << endl;
    for(int j : aho[now].accept) {
      //cout << j << " " << s[j] << endl;
      dp[i+1] += dp[i-s[j].size()+1];
      dp[i+1] %= mod;
    }
  }
  cout << dp[L] << endl;

  return 0;
}


```