初始你有一个串 $S$ 与 $n$ 个长度均为 $m$ 的串 $t_i$，还有一个长度为 $k$ 的实数序列 $p$ 满足和恰好为 $1$。保证 $S,t_i$ 均只包含前 $k$ 个小写字母。接下来你会进行以下操作：

• 若当前存在一个串 $t_i$ 满足它出现在 $S$ 中，那么操作结束。否则执行下面的第二条操作。
• 以 $p_i$ 的概率选中第 $i$ 小的小写字母，然后将它加到 $S$ 后面。这样会使 $S$ 长度扩张 $1$，然后返回上面第一条操作。

定义 $f(S,t,p)$ 为上述操作结束时 $S$ 的期望长度。你的任务是，给定 $t_{1...n},p_{1...k}$ 以及一个串 $R$。对每一个 $i(1\leq i\leq |R|)$，求出 $f(R[1\sim i],t,p) \bmod (10^9+7)$。

数据保证答案在 $\bmod (10^9+7)$ 意义下存在。

输入格式

第一行包含三个整数 $n,m,k$。

接下来一行包含 $k$ 个正整数 $P_i$ 表示选中第 $i$ 小的小写字母的概率为 $\frac{P_i}{100}$，保证 $\sum P_i=100$。

接下来 $n$ 行每行一个长度为 $m$ 的字符串，仅由前 $k$ 小的小写字母组成。

接下来一行一个字符串 $R$。

输出格式

输出 $|R|$ 行，每行输出一个非负整数表示答案。

样例输入 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

数据范围

对于 $100\%$ 的数据，$1\leq n\leq 100,1\leq n\times m\leq 10^4,1\leq k\leq 26,1\leq |R|\leq 10^4$。

各测试包的附加限制如下表所示：