Public Judge

pjudge

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100
[+2]
Statistics

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

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

定义 f(S,t,p) 为上述操作结束时 S 的期望长度。你的任务是,给定 t1...n,p1...k 以及一个串 R。对每一个 i(1i|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 无特殊限制