给定一个字符串 $S$，$n$ 个长度为 $m$ 的字符串 $T_1, T_2, \dots, T_n$，以及一个长度为 $k$ 且和为 1 的正有理数序列 $p$。每个字符串仅由前 $k$ 个小写字母组成。执行以下过程：

1. 如果存在 $j$ ($1 \le j \le n$) 使得 $T_j$ 是 $S$ 的子串，则停止过程。
2. 以概率 $p_i$ 将第 $i$ 个小写字母追加到 $S$ 的末尾，然后返回第 1 步。

定义 $f(S; T, p)$ 为过程停止时 $S$ 的期望长度。

计算单个字符串 $S$ 的 $f(S; T, p)$ 是无聊的。为了增加难度，给定一个字符串 $R$。记 $R$ 的长度为 $i$ 的前缀为 $R[1 \dots i]$。你的任务是计算对于 $i = 1, 2, \dots, |R|$ 的 $f(R[1 \dots i]; T, p)$。

可以证明 $f(S; T, p)$ 是一个正有理数，可以表示为 $\frac{P}{Q}$，其中 $\gcd(P, Q) = 1$。题目保证对于输入中给定的所有 $T$ 和 $p$ 下的字符串 $S$，均有 $Q \not\equiv 0 \pmod{10^9 + 7}$。你需要输出 $P Q^{-1} \pmod{10^9 + 7}$ 的值。

输入格式

第一行包含三个正整数 $n, m$ 和 $k$ ($1 \le n \le 100, n \times m \le 10\,000, 1 \le k \le 26$)。

第二行包含 $k$ 个正整数 $p'_1, p'_2, \dots, p'_k$。保证 $p'_1 + p'_2 + \dots + p'_k = 100$，且概率 $p_i$ 等于 $\frac{p'_i}{100}$。

接下来的 $n$ 行，第 $i$ 行包含一个长度为 $m$ 的字符串 $T_i$。

最后一行包含一个字符串 $R$ ($1 \le |R| \le 10\,000$)。

题目保证每个字符串仅由前 $k$ 个小写字母组成，且对于输入中给定的所有 $T$ 和 $p$ 下的字符串 $S$，当将 $f(S; T, p)$ 表示为 $\gcd(P, Q) = 1$ 的 $\frac{P}{Q}$ 时，均有 $Q \not\equiv 0 \pmod{10^9 + 7}$。

输出格式

输出 $|R|$ 行。第 $i$ 行包含一个整数，表示 $f(R[1 \dots i]; T, p)$ 的值。

样例

样例输入 1

2 2 2
50 50
aa
bb
ababaa

样例输出 1

3
4
5
6
7
6

样例输入 2

3 3 3
25 25 50
abc
bac
cab
ababbabbcaaa

样例输出 2

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

样例输入 3

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

样例输出 3

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