Untitled

struct trie
{
    int t[26];
    bool isEnd;
    trie()
    {
        mem(t, 0);
        isEnd = false;
    }
};
 
trie child[INF];
int dp[INF], n, cnt = 0;
string s;
 
void add(const string &s)
{
    int u = 0;
    for(char c : s)
    {
        int i = c - 'a';
        if(child[u].t[i] == 0)
        {
            child[u].t[i] = ++ cnt;
        }
        u = child[u].t[i];
    }
    child[u].isEnd = true;
}
 
void check(int i)
{
    int u = 0;
    FOR(j, i, s.size())
    {
        int index = s[j] - 'a';
        if(child[u].t[index] == 0) break;
        u = child[u].t[index];
        if(child[u].isEnd)
        {
            dp[j + 1] = (dp[j + 1] + dp[i]) % mod;
        }
    }
}
 
void nhap()
{
    cin >> n;
 
}
 
void solve()
{
    nhap();
    FOR(i, 0, n)
    {
        string w;
        cin >> w;
        add(w);
    }
    cin >> s;
    dp[0] = 1;
    FOR(i, 0, s.size())
    {
        if(dp[i] > 0)
        {
            check(i);
        }
    }
    cout << dp[s.size()];
}