Migrated from Lutece 3221 神秘的树

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

Tag: 另类拉格朗日反演，多项式高次幂远处系数求值

给定一个不包含 $1$ 的正整数集 $S$。

定义一个树是神秘的当且仅当对于每个非叶节点，他的孩子数属于这个数集 $S$。

给定 $S,M,T$。

$T$ 组询问，询问有多少叶节点数为 $n$ 的神秘的树，对 $M$ 取模。

Input

第一行三个正整数 $T,K,M$，表示询问的次数，$S$ 中数的范围，模数。

第二行一个长为 $K-1$ 的 01 串，第 $i$ 位（从 1 开始）表示 $i+1$ 是否在 $S$ 中，1/0 表示 在/不在。

接下来 $T$ 行，每行一个正整数 $n$，表示询问。

Output

输出 $T$ 行，每行一个正整数表示答案。

Samples

5 2 47
1
1
2
3
4
5

1
1
2
5
14

10 15 50
11101010101101
1
2
3
4
5
10
100
10000
998244353
1145141919810

1
1
3
11
44
27
31
30
10
26

Constraints

$1\le T \le 100$

$2\le K,M\le 50$

$1\le n\le 10^{18}$

Resources

2024 UESTC ICPC Training for Math