#include <bits/stdc++.h>

using ll = long long;

template <typename T> T inf;
template <> constexpr int inf<int> = 1e9;
template <> constexpr ll inf<ll> = 1e18;

constexpr int M = 1e9 + 7;


class aho_corasick {
    struct PMA {
        std::weak_ptr<PMA> fail;
        std::vector<std::shared_ptr<PMA>> next;
        std::vector<int> accept;

        PMA()
            : fail(), next(alphabets)
        {}
    };

public:
    aho_corasick(std::vector<std::string> const& ts)
        : K(ts.size()), root(std::make_shared<PMA>())
    {
        root->fail = root;
        for(int i = 0; i < K; ++i) {
            PMA* t = root.get();
            for(auto cc : ts[i]) {
                int c = cc - alphabet_base;
                if(!t->next[c]) {
                    t->next[c] = std::make_shared<PMA>();
                }
                t = t->next[c].get();
            }
            t->accept.push_back(i);
        }

        std::queue<std::shared_ptr<PMA>> que;
        for(int c = 0; c < alphabets; ++c) {
            if(root->next[c]) {
                root->next[c]->fail = root;
                que.push(root->next[c]);
            }
        }
        while(!que.empty()) {
            auto t = que.front();
            que.pop();
            for(int c = 0; c < alphabets; ++c) {
                if(t->next[c]) {
                    que.push(t->next[c]);
                    // assert(!t->fail.expired());
                    auto r = t->fail.lock();
                    while(!r->next[c] && r != root) {
                        r = r->fail.lock();
                    }
                    auto& nxt = r->next[c];
                    if(!nxt) { // root
                        nxt = root;
                    }
                    t->next[c]->fail = nxt;
                    for(auto ac : nxt->accept) {
                        t->next[c]->accept.push_back(ac);
                    }
                }
            }
        }
    }

    std::vector<std::vector<int>> match(std::string const& s, std::vector<std::string> const& ts, ll& cnt) {
        std::vector<std::vector<int>> res(K);
        std::vector<ll> dp(s.size() + 1);
        dp[0] = 1;
        PMA* now = root.get();
        for(int i = 0; i < (int)s.size(); ++i) {
            int c = s[i] - alphabet_base;
            while(!now->next[c] && now != root.get()) {
                now = now->fail.lock().get();
            }
            now = now->next[c].get();
            if(now == nullptr) {
                now = root.get();
            }
            for(auto k : now->accept) {
                //res[k].push_back(i);
                (dp[i + 1] += dp[i - ts[k].size() + 1]) %= M;
            }
        }
        cnt = dp[s.size()];
        return res;
    }

private:
    static int const alphabets = 26;      // a-z
    static int const alphabet_base = 'a'; // a
    int const K;
    std::shared_ptr<PMA> root;
};


using namespace std;
int main() {
    int N;
    cin >> N;
    string t;
    vector<string> s(N);
    for(int i = 0; i < N; ++i) {
        cin >> s[i];
    }
    cin >> t;

    aho_corasick aho(s);
    ll res = 0;
    auto match_pos = aho.match(t, s, res);
    cout << res << endl;
}


### 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 ll = long long;

template <typename T> T inf;
template <> constexpr int inf<int> = 1e9;
template <> constexpr ll inf<ll> = 1e18;

constexpr int M = 1e9 + 7;


class aho_corasick {
    struct PMA {
        std::weak_ptr<PMA> fail;
        std::vector<std::shared_ptr<PMA>> next;
        std::vector<int> accept;

        PMA()
            : fail(), next(alphabets)
        {}
    };

public:
    aho_corasick(std::vector<std::string> const& ts)
        : K(ts.size()), root(std::make_shared<PMA>())
    {
        root->fail = root;
        for(int i = 0; i < K; ++i) {
            PMA* t = root.get();
            for(auto cc : ts[i]) {
                int c = cc - alphabet_base;
                if(!t->next[c]) {
                    t->next[c] = std::make_shared<PMA>();
                }
                t = t->next[c].get();
            }
            t->accept.push_back(i);
        }

        std::queue<std::shared_ptr<PMA>> que;
        for(int c = 0; c < alphabets; ++c) {
            if(root->next[c]) {
                root->next[c]->fail = root;
                que.push(root->next[c]);
            }
        }
        while(!que.empty()) {
            auto t = que.front();
            que.pop();
            for(int c = 0; c < alphabets; ++c) {
                if(t->next[c]) {
                    que.push(t->next[c]);
                    // assert(!t->fail.expired());
                    auto r = t->fail.lock();
                    while(!r->next[c] && r != root) {
                        r = r->fail.lock();
                    }
                    auto& nxt = r->next[c];
                    if(!nxt) { // root
                        nxt = root;
                    }
                    t->next[c]->fail = nxt;
                    for(auto ac : nxt->accept) {
                        t->next[c]->accept.push_back(ac);
                    }
                }
            }
        }
    }

    std::vector<std::vector<int>> match(std::string const& s, std::vector<std::string> const& ts, ll& cnt) {
        std::vector<std::vector<int>> res(K);
        std::vector<ll> dp(s.size() + 1);
        dp[0] = 1;
        PMA* now = root.get();
        for(int i = 0; i < (int)s.size(); ++i) {
            int c = s[i] - alphabet_base;
            while(!now->next[c] && now != root.get()) {
                now = now->fail.lock().get();
            }
            now = now->next[c].get();
            if(now == nullptr) {
                now = root.get();
            }
            for(auto k : now->accept) {
                //res[k].push_back(i);
                (dp[i + 1] += dp[i - ts[k].size() + 1]) %= M;
            }
        }
        cnt = dp[s.size()];
        return res;
    }

private:
    static int const alphabets = 26;      // a-z
    static int const alphabet_base = 'a'; // a
    int const K;
    std::shared_ptr<PMA> root;
};


using namespace std;
int main() {
    int N;
    cin >> N;
    string t;
    vector<string> s(N);
    for(int i = 0; i < N; ++i) {
        cin >> s[i];
    }
    cin >> t;

    aho_corasick aho(s);
    ll res = 0;
    auto match_pos = aho.match(t, s, res);
    cout << res << endl;
}


```