#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <cstring>
#include <queue>
using namespace std;
typedef long long int lli;
const lli mod = 1e9+7;

struct AhoCorasick{
    static const int charsiz = 128;
    struct Node{
        vector<int> matched;
        int next[charsiz];
        Node() {
            memset(next, 0, sizeof(next));
        }
    };
    
    vector<Node> automaton;
    vector<string> patterns;
    
    AhoCorasick(){}
    AhoCorasick(vector<string> &s){
        patterns = s;
        build();
    }
    
    void build(){
        make_trie();
        make_failure_path();
    }
    void make_trie(){
        automaton.emplace_back();
        for(int i=0; i<(int)patterns.size(); i++){
            int curr = 0;
            for(int c: patterns[i]){ 
                if(automaton[curr].next[c] == 0){
                    automaton[curr].next[c] = automaton.size();
                    automaton.emplace_back();
                }
                curr = automaton[curr].next[c];
            }
            automaton[curr].matched.push_back(i);
        }
    }
    void make_failure_path(){
        queue<int> wait;
        wait.push(0);
        while(!wait.empty()){
            int curr = wait.front();
            wait.pop();
            for(int i=1; i<charsiz; i++){
                int next_i = automaton[curr].next[i];
                if(next_i != 0){
                    int fail = automaton[curr].next[0];
                    while(fail!=0 and automaton[fail].next[i]==0){
                        fail = automaton[fail].next[0];
                    }
                    if(fail == curr){
                        automaton[next_i].next[0] = 0;
                    }else{
                        automaton[next_i].next[0] = automaton[fail].next[i];
                    }
                    wait.push(next_i);
                }
            }
            insertvec(automaton[curr].matched,
                      automaton[automaton[curr].next[0]].matched);
        }
    }
    vector<vector<int>> match(string &t){
        vector<vector<int>> res(patterns.size());
        int curr = 0;
        for(int i=0; i<(int)t.length(); i++){
            while(curr!=0 and automaton[curr].next[(int)t[i]]==0){
                curr = automaton[curr].next[0];
            }
            curr = automaton[curr].next[(int)t[i]];
            
            for(int j: automaton[curr].matched){
                int len = patterns[j].length();
                res[j].push_back(i-len+1);
            }
        }
        return res;
    }
    vector<int> match_seq(string &t){
        vector<int> res(t.length());
        int curr = 0;
        for(int i=0; i<(int)t.length(); i++){
            while(curr!=0 and automaton[curr].next[(int)t[i]]==0){
                curr = automaton[curr].next[0];
            }
            curr = automaton[curr].next[(int)t[i]];
            res[i] = curr;;
        }
        return res;
    }
    
    template<class T>
    void insertvec(vector<T> &a, const vector<T> &b){
        a.insert(a.end(), b.begin(), b.end());
    }
};

int main(){
    int n;
    cin >> n;
    
    vector<string> s(n);
    for(int i=0; i<n; i++){
        cin >> s[i];
    }
    string t;
    cin >> t;
    AhoCorasick ac(s);
    auto ret = ac.match_seq(t);
    
    vector<vector<int>> matchlen(t.length());
    for(int i=0; i<(int)t.length(); i++){
        for(int strid: ac.automaton[ret[i]].matched){
            int len = s[strid].length();
            matchlen[i-len+1].push_back(len);
        }
    }
    vector<lli> dp(t.length()+1, 0);
    dp[0] = 1;
    for(int i=0; i<(int)t.length(); i++){
        for(int j: matchlen[i]){
            dp[i+j] = (dp[i+j] + dp[i]) %mod;
        }
    }
    cout << dp.back() << 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 <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <cstring>
#include <queue>
using namespace std;
typedef long long int lli;
const lli mod = 1e9+7;

struct AhoCorasick{
    static const int charsiz = 128;
    struct Node{
        vector<int> matched;
        int next[charsiz];
        Node() {
            memset(next, 0, sizeof(next));
        }
    };
    
    vector<Node> automaton;
    vector<string> patterns;
    
    AhoCorasick(){}
    AhoCorasick(vector<string> &s){
        patterns = s;
        build();
    }
    
    void build(){
        make_trie();
        make_failure_path();
    }
    void make_trie(){
        automaton.emplace_back();
        for(int i=0; i<(int)patterns.size(); i++){
            int curr = 0;
            for(int c: patterns[i]){ 
                if(automaton[curr].next[c] == 0){
                    automaton[curr].next[c] = automaton.size();
                    automaton.emplace_back();
                }
                curr = automaton[curr].next[c];
            }
            automaton[curr].matched.push_back(i);
        }
    }
    void make_failure_path(){
        queue<int> wait;
        wait.push(0);
        while(!wait.empty()){
            int curr = wait.front();
            wait.pop();
            for(int i=1; i<charsiz; i++){
                int next_i = automaton[curr].next[i];
                if(next_i != 0){
                    int fail = automaton[curr].next[0];
                    while(fail!=0 and automaton[fail].next[i]==0){
                        fail = automaton[fail].next[0];
                    }
                    if(fail == curr){
                        automaton[next_i].next[0] = 0;
                    }else{
                        automaton[next_i].next[0] = automaton[fail].next[i];
                    }
                    wait.push(next_i);
                }
            }
            insertvec(automaton[curr].matched,
                      automaton[automaton[curr].next[0]].matched);
        }
    }
    vector<vector<int>> match(string &t){
        vector<vector<int>> res(patterns.size());
        int curr = 0;
        for(int i=0; i<(int)t.length(); i++){
            while(curr!=0 and automaton[curr].next[(int)t[i]]==0){
                curr = automaton[curr].next[0];
            }
            curr = automaton[curr].next[(int)t[i]];
            
            for(int j: automaton[curr].matched){
                int len = patterns[j].length();
                res[j].push_back(i-len+1);
            }
        }
        return res;
    }
    vector<int> match_seq(string &t){
        vector<int> res(t.length());
        int curr = 0;
        for(int i=0; i<(int)t.length(); i++){
            while(curr!=0 and automaton[curr].next[(int)t[i]]==0){
                curr = automaton[curr].next[0];
            }
            curr = automaton[curr].next[(int)t[i]];
            res[i] = curr;;
        }
        return res;
    }
    
    template<class T>
    void insertvec(vector<T> &a, const vector<T> &b){
        a.insert(a.end(), b.begin(), b.end());
    }
};

int main(){
    int n;
    cin >> n;
    
    vector<string> s(n);
    for(int i=0; i<n; i++){
        cin >> s[i];
    }
    string t;
    cin >> t;
    AhoCorasick ac(s);
    auto ret = ac.match_seq(t);
    
    vector<vector<int>> matchlen(t.length());
    for(int i=0; i<(int)t.length(); i++){
        for(int strid: ac.automaton[ret[i]].matched){
            int len = s[strid].length();
            matchlen[i-len+1].push_back(len);
        }
    }
    vector<lli> dp(t.length()+1, 0);
    dp[0] = 1;
    for(int i=0; i<(int)t.length(); i++){
        for(int j: matchlen[i]){
            dp[i+j] = (dp[i+j] + dp[i]) %mod;
        }
    }
    cout << dp.back() << endl;
    return 0;
};


```