ml3 | All the Emojis!

This was the problem page during the contest. Access the current page here.
Time limit: 0.5s Memory limit: 64MB Input: Output:

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 MM symbols, mapping the ii-th of which to a sequence AiA_i, composed only of lowercase letters.

Edoardo has received a message SS, composed of NN 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=7M = 7:

YaY \rightarrow a; eabe \rightarrow ab; sbcs \rightarrow bc; !c! \rightarrow c; NaaN \rightarrow aa; obbo \rightarrow bb; ?cc? \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 SS can be interpreted.

Input data

The first line contains two integers NN and MM, the number of lowercase letters in the received message and the number of different symbols in their encoding. The second line contains a string SS composed of NN lowercase letters of the English alphabet, the message received by Edoardo. Further MM lines follow, the ii-th of which containing a string AiA_i composed of lowercase letters, the mapping of the ii-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 109+710^9 + 7.

Constraints and clarifications

  • 1N4 0001 \leq N \leq 4 \ 000.
  • 1M4 0001 \leq M \leq 4 \ 000.
  • 1AiN1 \leq |A_i| \leq N, for each i=0M1i = 0 \leq M - 1.
  • AiAjA_i \neq A_j for each iji \neq j.
# Score Constraints
1 0 Examples
2 15 N20N \leq 20, M2M \leq 2.
3 12 Ai=1A_i = 1 or Ai=1A_i = -1 for each i=0M1i = 0 \dots M - 1.
4 18 N500N \leq 500, M500M \leq 500.
5 24 SS and AiA_i are composed only of the letter a, for each i=0M1i = 0 \leq M - 1.
6 31 No additional limitations.

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: aabba|ab|b; aabba|a|bb; aabba|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!

Log in or sign up to be able to send submissions!