Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], skipTags: ["script","noscript","style","textarea","code"], processEscapes: true }});

Separate String

  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$.

Sample Input 1

3
a
b
ab
abab

Output for Sample Input 1

4

Sample Input 2

3
a
b
c
xyz

Output for Sample Input 2

0

Sample Input 3

7
abc
ab
bc
a
b
c
aa
aaabcbccababbc

Output for Sample Input 3

160

Sample Input 4

10
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaaa
aaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Output for Sample Input 4

461695029



Sample input:
3
a
b
ab
abab


Sample output:
4

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
def solve():
    readline = sys.stdin.readline
    write = sys.stdout.write
    mod = 10**9 + 9
    base = 37
    ca = ord('a')

    N = int(readline())
    SS = [readline().strip() for i in range(N)]
    SS.sort(key = len)

    T = readline().strip()
    L = len(T)

    L0 = max(max(map(len, SS)), L)

    r = 1
    pw = [1]*(L0+1)
    for i in range(L0):
        pw[i+1] = r = r * base % mod

    SM = defaultdict(dict)
    E = [None]*N
    for i in range(N):
        s = SS[i][::-1]
        h = 0
        p = -1
        for j, c in enumerate(s):
            h = (h + pw[j] * (ord(c) - ca)) % mod
            if j+1 in SM and h in SM[j+1]:
                p = SM[j+1][h]
        l = len(s)
        E[i] = (E[p] + [l]) if p != -1 else [l]
        SM[l][h] = i

    *SI, = SM.items()
    SI.sort()
    H = [0]*(L+1)
    r = 0
    for i, c in enumerate(T):
        H[i+1] = r = (base * r + (ord(c) - ca)) % mod

    MOD = 10**9 + 7
    dp = [0]*(L+1)
    dp[0] = 1
    SI.append((L+10, set()))
    it = iter(SI).__next__
    ln, sn = it()
    SL = []
    for i in range(1, L+1):
        if i == ln:
            SL.append((ln, sn, pw[ln]))
            ln, sn = it()
        hi = H[i]
        for l, hs, w in reversed(SL):
            v = (hi - H[i-l]*w) % mod
            if v in hs:
                dp[i] = sum(dp[i-e] for e in E[hs[v]]) % MOD
                break
    write("%d\n" % dp[L])
solve()