MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 16px; line-height: 18px; background-color: #f5f5f5; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }

Problem Statement

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$ $\\vdots$ $s\_N$ $t$

The first line consists of an integer $N \\ (1 \\le N \\le 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 \\le i \\le 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