Problem Description

Tomoki is trying to learn a new spell from Tenkaichi-ou Kingdom's magic.

Tomoki chants spells by combining the phrases he remembers.

He can use the same phrase multiple times in a spell.

For example, if he remembers three phrases: $aaa,\ bbb,\$, he can chant spells like $aaaccc,\ aaabbb,\$.

Tomoki is worried whether he can compose the new spell he is trying to learn by combining the phrases he remembers.

Create a program to count how many ways there are to arrange the phrases to construct the spell.

Since the number of arrangements can be large, output the result modulo $ 1000000007 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ S $ $ T1 $ $ T2 $ : $ TN $

• The first line contains the number of phrases Tomoki remembers, $N\ (1\ \leq\ N\ \leq\ 100)$.
• The second line contains the spell $ S $ that Tomoki wants to learn.
• The length of $ S $, $ |S| $, satisfies $1\ \leq\ |S|\ \leq\ 1000$.

• $ S $ consists of lowercase alphabets.

• From the third line to the $ N $th line, the phrases $ Ti $ that Tomoki remembers are given.

• The length of $ Ti $, $ |Ti| $, satisfies $1\ \leq\ |Ti|\ \leq\ 1000$.
• $ Ti $ consists of lowercase alphabets.
• $Ti\ \neq\$ if $i\ \neq\ j$.

Output Format

Output the number of ways to arrange the phrases to construct the spell modulo $ 1000000007 $ in one line. Include a newline at the end of the output.

Sample Input and Output

Sample Input #1

3
eternalstaticfinal
eternal
static
final

Sample Output #1

1

Sample Input #2

5
eternalstaticfinal
eternal
static
final
fin
al

Sample Output #2

2

Sample Input #3

5
abcdef
abc
def
abcdef
d
ef

Sample Output #3

3

Sample Input #4

5
aaaa
a
aa
aaa
aaaa
b

Sample Output #4

8

Sample Input #5

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

Sample Output #5

146491918

Notes/Hints

Sample Explanation 1

There is only one way to arrange the phrases.

Sample Explanation 2

There are two ways to arrange the phrases as follows:

eternal + static + final
eternal + static + fin + al

Sample Explanation 3

There are three ways to arrange the phrases as follows:

abcdef
abc + def
abc + d + ef

Sample Explanation 4

There are eight ways to arrange the phrases as follows:

aaaa
aaa + a
aa + aa
aa + a + a
a + aaa
a + aa + a
a + a + aa
a + a + a + a

Tomoki's remembered phrase b was not used in this spell.

Sample Explanation 5

Since the number of arrangements can be large, output the result modulo $ 1000000007 $.

见题面 Input 部分

见题面 Output 部分