初始你有一个串 $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$。
各测试包的附加限制如下表所示：
| 子任务编号 | 得分 | 限制 |
|---|---|---|
| 1 | 5 | $k=1$ |
| 2 | 10 | $k=2$ |
| 3 | 30 | $n\times m \leq 500$ |
| 4 | 55 | 无特殊限制 |