J. 小Q的机器
time limit per test
2 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

小Q有一个神奇的机器，可以随机生成某个长度的字符串（包括长度为$$$0$$$的空串）。字符串的不同位之间相互独立，同一字符在任一位上出现的概率都是相同的。

小Q发现了一个自己很喜欢的字符串$$$S$$$，他希望知道如果他让机器生成一个长度为$$$k$$$的字符串，$$$S$$$是该字符串的子序列的概率是多少。 一个字符串的子序列是指从该字符串中取部分字符（可以全取或全不取），取出来的字符按在原串中的顺序排列而成的字符序列。如空串、"aba"、"aac"、"ababc"都是"ababc"的子序列，而"cab"则不是。

Input

第一行$$$26$$$个非负数，表示从'a'到'z'每个字符的权重，即输入$$$weight['a'..'z'](0 \le weight[i] \le 1000)$$$，字符$$$ch$$$在任一位上出现的概率为 $$$$$$ \frac{weight[ch]}{\sum_{i='a'}^{i='z'}weight[i]} $$$$$$

第二行一个字符串 $$$S(1\le |S| \le 100)$$$。

第三行一个正整数 $$$T(1\le T \le 100)$$$，表示数据组数。

接下来$$$T$$$行，每一个一个正整数 $$$k(0\le k \lt 2^{60})$$$，表示机器生成的字符串长度。

保证至少有一个$$$weight[i]$$$不为$$$0$$$。

Output

$$$T$$$行，每行一个正整数，表示$$$S$$$是该字符串的子序列的概率，对$$$998244353$$$取模的结果。

可以证明答案一定可以表示成 $$$\frac{q}{p}$$$，其中$$$q$$$为非负整数，$$$p$$$为正整数，且存在一个正整数$$$p^{(-1)}$$$，使得 $$$p^{(-1)}×p≡1\ mod\ 998244353$$$，即$$$p$$$在模$$$998244353$$$下一定存在逆元，你只需输出$$$q×p^{(-1)}$$$模$$$998244353$$$的值即可。

Example
Input
30 40 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
abc
6
0
1
2
3
4
5
Output
0
0
0
387318809
163712074
688748674
Note

$$$a$$$在每一位上出现的概率为$$$0.3$$$，$$$b$$$为$$$0.4$$$，$$$c$$$为$$$0.3$$$，其余字符不可能出现。

$$$k=0$$$时，只能生成空串，$$$k=1,2$$$时，长度小于$$$3$$$，不可能包含子序列"abc"。

$$$k=3$$$时，长度为$$$3$$$的串只有abc，概率为$$$0.3·0.4·0.3=0.036$$$，模$$$998244353$$$为$$$387318809$$$。

$$$k=4$$$时，长度为$$$4$$$的串中abc*,ab*c,a*bc,*abc符合条件，计算得概率为$$$0.1080$$$，模$$$998244353$$$为$$$163712074$$$。

$$$k=5$$$时，概率为$$$0.20412$$$，模$$$998244353$$$为$$$688748674$$$。