Reading the stone slab

Seongwon was excavating an ancient site when he found a large stone slab, and he is decoding the text carved on it so he can report the find. Centuries of weather have worn the letters down, so many of them are hard to make out.

When the slab was carved, people liked to put the king's name on it. A slab counted as better the more ways there were to pick some of its letters (they do not have to be adjacent) and read them in order as the king's name. People also disliked long speech, so a king's name was never more than 5 letters.

Dating the slab told Seongwon which king reigned when it was buried, and now he wants to know how many ways that name can be read off the slab. The carving is faint, so as the study goes on the reading of parts of the slab keeps changing, and he wants the count again after every change. Help Seongwon by writing a program that computes it.

The first line contains the number of test cases $T$ ($1 \le T \le 10$).

The first line of each test case contains the number of letters on the slab $N$ ($1 \le N \le 200000$), the length of the king's name $M$ ($1 \le M \le 5$), and the number of times the reading of the slab changes $Q$ ($0 \le Q \le 100000$). The second line contains the first reading of the slab as a single string of uppercase English letters. The third line contains the king's name as a single string, also of uppercase English letters.

Each of the next $Q$ lines contains two integers $A_i$, $B_i$ and a string $S_i$ ($1 \le A_i \le B_i \le N$, the length of $S_i$ is $B_i - A_i + 1$). This means the reading of the slab from its $A_i$-th letter through its $B_i$-th letter becomes $S_i$. Every $S_i$ consists of uppercase English letters as well, and the total length of all $S_i$ over all test cases is at most 2000000.

For each test case print $Q + 1$ lines, one integer per line. On line $i$ print the number of ways to read the king's name off the $i$-th reading of the slab. The answer can be large, so print it modulo 1000000007.