Problem:
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

Solution (Python):
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()