408445: GYM103119 B Boring Problem

B. Boring Problemtime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

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:

1. If there exists $$$j$$$ $$$(1\leq j\leq n)$$$ such that $$$T_j$$$ is a substring of $$$S$$$, stop the procedure.
2. 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)$$$.

ExamplesInput

2 2 2
50 50
aa
bb
ababaa

Output

3
4
5
6
7
6

Input

3 3 3
25 25 50
abc
bac
cab
ababbabbcaaa

Output

13
333333343
333333344
333333345
17
333333347
333333348
20
333333358
666666692
23
24

Input

4 4 4
10 20 30 40
abcb
cabc
abbb
cccc
ababacabaabcca

Output

146386692
32395942
146386694
32395944
146386696
851050282
242422295
512573933
146386700
146386701
32395951
66073407
572924730
242422302