初始你有一个串 S 与 n 个长度均为 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(1≤i≤|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 | 无特殊限制 |