ml3 | All the Emojis!

William and Edoardo are using a new instant messaging app to communicate. However, the application only supports messages composed exclusively of lowercase letters of the English alphabet. They are avid emoji users, so this is clearly unacceptable!

For this reason, they devised a way to convert any message to a string that can be sent using the app: any symbol in the original message is mapped to a sequence of one or more lowercase letters and this encoding is known to both of them. The encoding is defined for $M$ symbols, mapping the $i$-th of which to a sequence $A_i$, composed only of lowercase letters.

Edoardo has received a message $S$, composed of $N$ lowercase letters, and now needs to translate it back to its original form. However, he realized that, in some cases, a message can be interpreted in multiple ways. This is a huge problem! For instance, consider the following encoding, where $M = 7$:

$Y \rightarrow a$; $e \rightarrow ab$; $s \rightarrow bc$; $! \rightarrow c$; $N \rightarrow aa$; $o \rightarrow bb$; $? \rightarrow cc$;

If the message is Yes!, William will actually send to Edoardo aabbcc. However, also the message No? is translated into aabbcc. What a mess! Help Edoardo count the number of different ways in which the message $S$ can be interpreted.

Input data

The first line contains two integers $N$ and $M$, the number of lowercase letters in the received message and the number of different symbols in their encoding. The second line contains a string $S$ composed of $N$ lowercase letters of the English alphabet, the message received by Edoardo. Further $M$ lines follow, the $i$-th of which containing a string $A_i$ composed of lowercase letters, the mapping of the $i$-th symbol in the encoding.

Output data

You need to write a single line with an integer: the number of different ways in which the received message can be interpreted. Since this number can be very big, calculate it modulo $10^9 + 7$.

Constraints and clarifications

• $1 \leq N \leq 4 \ 000$.
• $1 \leq M \leq 4 \ 000$.
• $1 \leq |A_i| \leq N$, for each $i = 0 \leq M - 1$.
• $A_i \neq A_j$ for each $i \neq j$.

Example 1

stdin

4 4
aabb
a
b
bb
ab

stdout

3

Explanation

In the first sample case, the message aabb can be interpreted in three ways: $a|ab|b$; $a|a|bb$; $a|a|b|b$;

Example 2

stdin

4 4
aabb
a
ab
aa
aba

stdout

0

Explanation

In the second sample case, the message cannot be interpreted in any way using the given mapping!