Separate String

Time limit2sMemory limit512 MB

Summary

Count the ways to split string t into a sequence of pieces, each of which is one of N given dictionary strings, modulo 1e9+7.

Level: Medium7 of 10
Topics: Dynamic programming, Trie, String matching, String
Solved: No attempts yet

Problem

You are given a string $t$ and a set $S$ of $N$ distinct strings. You must split $t$ into pieces so that every piece is an element of $S$ .

For example, when $t$ = abab and $S$ = {a, ab, b}, the following 4 splittings satisfy the condition.

a, b, a, b
a, b, ab
ab, a, b
ab, ab

Count the number of ways to split $t$ . The answer can be very large, so print the remainder after dividing it by 1,000,000,007.

Input

The input consists of a single test case in the following format.

N
s1
.
.
.
sN
t

The first line contains an integer $N$ ( $1 \le N \le 100{,}000$ ), the number of elements of $S$ . The next $N$ lines contain $N$ distinct strings, one per line. The $i$ -th string $s_i$ is the $i$ -th element of $S$ . Each $s_i$ consists of lowercase letters and has length between 1 and 100,000, inclusive. The sum of the lengths of all $s_i$ ( $1 \le i \le N$ ) is at most 200,000. The last line contains the string $t$ to be split. $t$ consists of lowercase letters and has length between 1 and 100,000, inclusive.

Output

Print the number of ways to split $t$ , modulo 1,000,000,007.

Examples4

Example 1
Input
```
3
a
b
ab
abab
```
Expected output
```
4
```
Example 2
Input
```
3
a
b
c
xyz
```
Expected output
```
0
```

Example 3

Input

7
abc
ab
bc
a
b
c
aa
aaabcbccababbc

Expected output

Example 4

Input

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

Expected output

461695029