It's the holiday season, thus following the family tradition, Benson has to follow his family on a trip overseas to some foreign nation. To prevent a very significant language barrier from ruining their fun, the language of said nation only contains alphabetical characters (unless it's Chinese).

However, this year's trip is very special. He also must attend a wedding dinner as his family was invited by the bride. Trying not to fall asleep during one of the speeches, he looks at a booklet given to all guests that contains the speeches that will be recited by the speakers. The speech that is currently being spoken has ~N~ characters (no spaces). To keep himself busy, Benson tries to follow the speaker using the booklet.

Problem is, not only does Benson not understand a single thing the speaker is saying, he also constantly loses track of where the speaker is. Fortunately, at ~P~ points during the speech, he hears a string of characters of length ~C_i~. These strings can repeat but come in the order Benson heard them. He will hear them in order of the first letter of the string heard.

For example, if he hears grapes then apesle and the speech contains grapesle, it counts as hearing both in order. However, apple counts as hearing apple then app if and only if Benson says he heard apple then app. In other words, if a heard string is a prefix of another, he will hear the first one that he said he heard first.

Now Benson wants to know how many ways he could have heard the strings in that order. As this number can be very big, he wants you to tell him the number's remainder when divided by ~1\,000\,000\,007~.

Input Specification

The first line contains ~N~ and ~P~.

The second line contains ~N~ characters, describing the speech Benson is listening to.

The next ~P~ lines contain a string of letters of length ~C_i~ each, which indicate the strings Benson heard during the speech.

Output Specification

Output the number of ways Benson could have heard the strings in order, modulo ~1\,000\,000\,007~.

Constraints

Subtask 1 [0%]

Sample test cases.

Subtask 2 [5%]

~1 \le N \le 50~

~1 \le P \le 5~

~1 \le C_i \le 10~

Subtask 3 [20%]

~1 \le N \le 5\,000~

~1 \le P \le 50~

~1 \le C_i \le 100~

Subtask 4 [75%]

~1 \le N \le 100\,000~

~1 \le P \le 100~

~1 \le C_i \le 5\,000~

Sample Input 1

38 4
hihoebinnejobinnejimoktankenhawwewille
o
nn
we
w

Sample Output 1

6

Sample Input 2

50 3
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
aaaaaaab
aaaaaab
aaaaa

Sample Output 2

2