November

题目描述

浮かべた言葉は 音も無く弾けた

あたしが恋した 色の無い街並み

もう一回と思ったのだ 此処にいるわけにいかないから

寂しくて唄ったのが これが僕と思えたんだ

—— November

给定一个初始字符串 $S$，以及 $n$ 个长度为 $m$ 的“终止模式串” $T_1, T_2, \dots, T_n$。此外，给定一个包含从 a 开始前 $k$ 个字符的字符集，每个字符生成的概率为 $p_1, p_2, \dots, p_k$。

生成流程如下：

1. 检查当前字符串 $S$ 是否包含任意一个终止模式串 $T_j$ 作为子串。
2. 如果包含，则停止程序。
3. 如果不包含，则根据概率分布 $p$ 随机选择一个字符，并将其追加到 $S$ 的末尾。
4. 返回步骤 1 继续循环。

定义 $f(S; T, p)$ 为在此流程下，字符串 $S$ 最终停止时的期望长度。

给出了一个长度为 $|R|$ 的字符串 $R$。你需要分别计算对于 $R$ 的每一个前缀 $R[1 \dots i]$（其中 $i = 1, 2, \dots, |R|$），如果将该前缀作为初始字符串 $S$，对应的期望长度是多少。

输入格式

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

第二行：$k$ 个正整数 $p'_1, p'_2, \dots, p'_k$，表示概率 $p_i = \frac{p'_i}{100}$。保证其和为 $100$。

接下来的 $n$ 行：每行一个长度为 $m$ 的字符串 $T_i$。

最后一行：一个字符串 $R$，表示初始前缀序列。

输出格式

输出 $|R|$ 行，每行一个整数，表示在模 $10^9 + 7$ 意义下的期望值。

样例

样例 1

2 2 2
50 50
aa
bb
ababaa

3
4
5
6
7
6

样例 2

3 3 3
25 25 50
abc
bac
cab
ababbabbcaaa

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

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

样例 4

见附加文件 nov4.in/nov4.out，该组数据满足 Subtask 1 的特殊限制。

样例 5

见附加文件 nov5.in/nov5.out，该组数据满足 Subtask 2 的特殊限制。

样例 6

见附加文件 nov6.in/nov6.out，该组数据满足 Subtask 3 的特殊限制。

样例 7

见附加文件 nov7.in/nov7.out，该组数据满足 Subtask 4 的特殊限制。

样例 8

见附加文件 nov8.in/nov8.out。

数据范围

对于所有数据 $n\le 100$，$nm\le 10000$，$k\le 26$，$|R|\le 10000$，字符集是前 $k$ 个小写字母。