Initially, you have a string $S$, $n$ strings $t_i$ each of length $m$, and a sequence of $k$ real numbers $p$ whose sum is exactly $1$. It is guaranteed that $S$ and all $t_i$ consist only of the first $k$ lowercase letters. You perform the following operations:

• If there exists a string $t_i$ that appears as a substring in $S$, the process terminates. Otherwise, proceed to the second operation.
• Select the $i$-th smallest lowercase letter with probability $p_i$, and append it to the end of $S$. This increases the length of $S$ by $1$, then return to the first operation.

Define $f(S, t, p)$ as the expected length of $S$ when the process terminates. Given $t_{1...n}$, $p_{1...k}$, and a string $R$, for each $i$ ($1 \leq i \leq |R|$), calculate $f(R[1 \sim i], t, p) \pmod{10^9+7}$.

It is guaranteed that the answer exists modulo $10^9+7$.

Input

The first line contains three integers $n, m, k$.

The next line contains $k$ positive integers $P_i$, representing that the probability of selecting the $i$-th smallest lowercase letter is $\frac{P_i}{100}$, where $\sum P_i = 100$.

The next $n$ lines each contain a string of length $m$, consisting only of the first $k$ lowercase letters.

The last line contains a string $R$.

Output

Output $|R|$ lines, each containing a non-negative integer representing the answer.

Examples

Input 1

2 2 2
50 50
aa
bb
ababaa

Output 1

3
4
5
6
7
6

Input 2

3 3 3
25 25 50
abc
bac
cab
ababbabbcaaa

Output 2

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

Input 3

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

Output 3

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

Constraints

For $100\%$ of the data, $1 \leq n \leq 100$, $1 \leq n \times m \leq 10^4$, $1 \leq k \leq 26$, $1 \leq |R| \leq 10^4$.

The additional constraints for each subtask are as follows: