Migrated from Lutece 2826 26面骰子

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

瓜皮大哥在232的一堆资料中找到了一个26面骰子，骰子的每个面 $i$ 对应一个字符 $i$。

但他发现，这个骰子的重心不太对，因此每次投掷骰子，骰子朝上的那面总会是前 $k$ 面中的一个面，并且每个面出现的概率不同。

由于瓜皮大哥出不出字符串题，因此他决定拿这个骰子给自动机中的猴子，让猴子给他一直扔骰子。

现在自动机中有 $n$ 个长度为 $m$ 的只由小写字符构成的字符串 $T_i$ , 现在有一个一开始为空的母串，你每次会随机在其末尾以 $P_i$ 的概率加入字符 $i$,当生成的字符串 $S$ 中存在一个 $T_i$ 为 $S$ 的子串时停止，求生成的字符串的期望长度。

但最初为空对大家来讲太简单了，因此他决定再加入一个限制条件，即一开始母串非空。

现在给你一个字符串 $R$ ，问你对于 $R$ 的每一个前缀， 上述问题的答案为多少。

Input

第一行输入三个整数 $n,m,k$

第二行输入 $k$ 个整数 $p_i$ ，表示第 $i$ 个字符的概率为 $\frac{p_i}{100}$ ，数据保证 $\sum_{i=1}^{k}{p_i}=100$

接下来 $n$ 行输入长度为 $m$ 只由前 $k$ 个小写字符组成的字符串。

接下来一行输入字符串 $R$

Output

输出 $|R|$ 行，每行输出当前母串为 $R[1,i]$ 时，$S$ 的期望长度，答案对 $10^9+7$ 取模。

Samples

2 2 2
50 50
aa
bb
ababaa

3
4
5
6
7
6

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

Constraints

$1≤n≤100, n\times m≤10000, 1≤k≤26 ,1≤|R|≤10000 ,1\le p_i \le 100$

Resources

2022 UESTC ICPC Training for String and Search Algorithm