P4591 [TJOI2018] Base Sequence

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.

- 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 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$.

### 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