Problem Description

Xiao Dou has participated in a biology lab. In the lab, he mainly studies proteins. The protein he is currently studying is composed of \( k \) amino acids in a certain order. Each amino acid can be formed by \( a \) different base sequences \( s_{i,j} \).

Now, Xiao Dou has a base string \( s \). He wants to know how many different combination methods can form this protein on this base string. That is, he needs to find out how many different ways there are to merge \( k \) segments of strings into a string \( s_1 \) that matches the string \( s \). Different methods are considered if the selection of the \( k \) segments is different, or if the matching positions with \( s \) are different.

Input Format

The first line contains a number, indicating that the protein is composed of \( k \) amino acids.

The second line contains a string \( s \), representing the base string Xiao Dou has.

The third line and onwards, for \( k \) lines, describe the possible base sequences for the \( i \)-th amino acid. For the \( i \)-th amino acid, \( a_i \) represents the number of possible base sequences, followed by \( a_i \) strings representing these possible base sequences, separated by spaces.

Output Format

Output a number representing the number of different schemes (different schemes refer to different sub-base strings or the same base string with different amino acid arrangements).

The answer should be modulo \( 10^9 + 7 \).

Sample Input and Output

Sample Input #1

2
ABC
2 A AB
2 C BC

Sample Output #1

2

Sample Input #2

2
AAA
2 A AA
2 A AA

Sample Output #2

4

Notes

Sample 1 Explanation

• Choosing \(\tt A\) first and \(\tt C\) second results in \(\tt AC\), which matches \(\tt ABC\) in 0 ways.
• Choosing \(\tt A\) first and \(\tt BC\) second results in \(\tt ABC\), which matches \(\tt ABC\) in 1 way.
• Choosing \(\tt AB\) first and \(\tt C\) second results in \(\tt ABC\), which matches \(\tt ABC\) in 1 way.
• Choosing \(\tt AB\) first and \(\tt BC\) second results in \(\tt ABBC\), which matches \(\tt ABC\) in 0 ways.

Thus, there are 2 ways in total.

Sample 2 Explanation

• Choosing \(\tt A\) first and \(\tt A\) second results in \(\tt AA\), which matches \(\tt AAA\) in 2 ways.
• Choosing \(\tt A\) first and \(\tt AA\) second results in \(\tt AAA\), which matches \(\tt AAA\) in 1 way.
• Choosing \(\tt AA\) first and \(\tt A\) second results in \(\tt AAA\), which matches \(\tt AAA\) in 1 way.
• Choosing \(\tt AA\) first and \(\tt AA\) second results in \(\tt AAAA\), which matches \(\tt AAA\) in 0 ways.

Thus, there are 4 ways in total.

Data Range and Constraints

• For 30% of the data, \( 1 \leq k \leq 25 \), \( 1 \leq |s| \leq 10000 \), \( 1 \leq a_i \leq 3 \).
• For 100% of the data, \( 1 \leq k \leq 100 \), \( 1 \leq |s| \leq 10000 \), \( 1 \leq a_i \leq 10 \). The length of each base sequence does not exceed 15. The character set is uppercase letters.

见题面 Input 部分

见题面 Output 部分