Description

Xiaodou joined a biology laboratory. In the lab, he mainly studies proteins. The protein he is currently studying consists of $k$ amino acids in a fixed order. For each amino acid $i$, there are $a_i$ possible base sequences $s_{i,j}$.

Now Xiaodou has a base string $s$, and he wants to know how many different combinations could produce this protein on this base string. That is, consider the string $s_1$ obtained by concatenating $k$ string segments in order, where for the $i$-th segment you choose one sequence from its $a_i$ options. Count how many different ways $s_1$ can match the string $s$ as a contiguous substring. Two ways are considered different if either the choices for the $k$ segments differ, or the matched positions in $s$ differ.

Input Format

• The first line contains an integer indicating that the protein consists of $k$ amino acids.
• The second line contains a string $s$, which is the current base string.
• The next $k$ lines describe the possible base sequences for the $i$-th amino acid. For the $i$-th amino acid, the line starts with $a_i$, the number of possible base sequences, followed by $a_i$ strings representing these possible base sequences, separated by spaces.

Output Format

Output a single integer: the number of different ways (either different substrings of $s$, or for the same substring, different choices of sequences for the amino acids). The answer is taken modulo $10^9+7$.

2
ABC
2 A AB
2 C BC

2

2
AAA
2 A AA
2 A AA

4

Hint

Sample 1 Explanation

• First choose $\tt A$, second choose $\tt C$, obtaining $\tt AC$, which matches $\tt ABC$ in $0$ ways.
• First choose $\tt A$, second choose $\tt BC$, obtaining $\tt ABC$, which matches $\tt ABC$ in $1$ way.
• First choose $\tt AB$, second choose $\tt C$, obtaining $\tt ABC$, which matches $\tt ABC$ in $1$ way.
• First choose $\tt AB$, second choose $\tt BC$, obtaining $\tt ABBC$, which matches $\tt ABC$ in $0$ ways.

Therefore there are $2$ ways in total.

Sample 2 Explanation

• First choose $\tt A$, second choose $\tt A$, obtaining $\tt AA$, which matches $\tt AAA$ in $2$ ways.
• First choose $\tt A$, second choose $\tt AA$, obtaining $\tt AAA$, which matches $\tt AAA$ in $1$ way.
• First choose $\tt AA$, second choose $\tt A$, obtaining $\tt AAA$, which matches $\tt AAA$ in $1$ way.
• First choose $\tt AA$, second choose $\tt AA$, obtaining $\tt AAAA$, which matches $\tt AAA$ in $0$ ways.

Therefore there are $4$ ways in total.

Constraints

• For $30\%$ of the testdata, $1 \le k \le 25$, $1 \le |s| \le 10000$, $1 \le a_i \le 3$.
• For $100\%$ of the testdata, $1 \le k \le 100$, $1 \le |s| \le 10000$, $1 \le a_i \le 10$. The length of each base sequence does not exceed $15$. The character set consists of uppercase letters.

Translated by ChatGPT 5