Untitled

const ll mod = 1e9 + 7;
const int inf = (int) 1000005;
const int base = (int) 131;
const ll m2 = 1LL * mod * mod;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int n, cnt = 0, dp[100005];
string s, w;

struct Trie
{
    int child[26];
    bool isEnd;
    Trie()
    {
        mem(child, 0);
        isEnd = false;
    }
};

vector<Trie> trie(inf);

void add(const string& s)
{
    int u = 0;
    for(char c : s)
    {
        int i = c - 'a';
        if(trie[u].child[i] == 0)
        {
            trie[u].child[i] = ++cnt;
        }
        u = trie[u].child[i];
    }
    trie[u].isEnd = true;
}

void check(const string&s, int start)
{
    int u = 0;
    FOR(i, start, s.size())
    {
        int id = s[i] - 'a';
        if(trie[u].child[id] == 0) break;
        u = trie[u].child[id];
        if(trie[u].isEnd)
        {
            //dp[i + 1] = (dp[i + 1] % mod + dp[start] % mod) % mod;
            dp[i + 1] = (dp[i + 1] + dp[start]) % mod;
        }
    }
}

void nhap()
{
    cin >> n;
}

void solve()
{
    nhap();
    FOR(i, 0, n)
    {
        cin >> w;
        add(w);
    }
    cin >> s;
    dp[0] = 1;
    FOR(i, 0, s.size())
    {
        if(dp[i] > 0)
        {
            check(s, i);
        }
    }
    cout << dp[s.size()];
}