Problem C
Boring Problem
Given a string $S$, $n$ strings $T_1,T_2,\dots ,T_n$ of length $m$ and a positive rational number sequence $p$ of length $k$ whose sum is $1$. Each string consists of only the first $k$ lowercase letters. Let’s perform the following procedure:
-
If there exists $j$ $(1\leq j\leq n)$ such that $T_j$ is a substring of $S$, stop the procedure.
-
Append the $i$-th lowercase letter with probability $p_i$ to the end of $S$, then return to step 1.
Let’s define $f(S;T,p)$ as the expected length of $S$ when the procedure stops.
It’s boring to calculate $f(S;T,p)$ for only one string $S$. To make the problem much harder, a string $R$ is given. Let’s denote the prefix of $R$ of length $i$ as $R[1\dots i]$. Your task is to calculate $f(R[1\dots i];T,p)$ for $i=1,2,\cdots ,|R|$.
It can be proved that $f(S;T,p)$ is a positive rational number and it can be represented as $\frac PQ$ with $\gcd (P,Q)=1$. It is guaranteed that $Q\not\equiv 0\pmod{(10^9+7)}$ for all strings $S$ under the given $T$ and $p$ in the input. You should print the value of $PQ^{-1}\mod (10^9+7)$.
Input
The first line contains three positive integers $n,m$ and $k$ ($1\leq n\leq 100$, $n\times m\leq 10\, 000$, $1\leq k\leq 26$).
The second line contains $k$ positive integers $p'_1,p'_2\cdots ,p'_k$. It is guaranteed that $p'_1+p'_2+\cdots +p'_k=100$ and the probability $p_i$ equals to $\frac{p'_i}{100}$.
The $i$-th line of the following $n$ lines contains a string $T_i$ of length $m$.
The last line contains a string $R$ ($1\leq |R|\leq 10\, 000$).
It is guaranteed each string consists of only the first $k$ lowercase letters and $Q\not\equiv 0\pmod{(10^9+7)}$ when representing $f(S;T,p)$ as $\frac PQ$ with $\gcd (P,Q)=1$ for all strings $S$ under the given $T$ and $p$ in the input.
Output
Ouput $|R|$ lines. The $i$-th line contains an integer representing the value of $f(R[1\dots i];T,p)$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 2 2 50 50 aa bb ababaa |
3 4 5 6 7 6 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 3 3 25 25 50 abc bac cab ababbabbcaaa |
13 333333343 333333344 333333345 17 333333347 333333348 20 333333358 666666692 23 24 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 4 4 10 20 30 40 abcb cabc abbb cccc ababacabaabcca |
146386692 32395942 146386694 32395944 146386696 851050282 242422295 512573933 146386700 146386701 32395951 66073407 572924730 242422302 |