Note. We distinguish the order of the children of a node.
带加强同学人如其名，喜欢加强各种计数题，尤其喜欢多项木。所谓多项木，就是“多项”+“木”，而“木”也有“树”之含义，也就是用多项式来数树。
带加强认为一颗有根树的稳定程度取决于这棵树的每个节点有几个孩子，于是他规定了一个正整数集合 $D$，称一颗有根树是“铁”的，当且仅当对于这棵树的每一个非叶节点，设其有 $x$ 个孩子，那么 $x\in D$。
带加强每次询问你一个 $n$，请你回答他有多少颗 $n$ 个叶子的有根树是“铁”的，答案对 $M$ 取模。
输入格式
第一行输入三个正整数 $T, K, M$，表示询问次数、集合中数的范围和模数。
接下来一行一个长为 $K-1$ 的 01 串，串中（从 $2$ 开始计数）第 $x$ 个数是 1 表示 $x\in D$，否则 $x\notin D$。
接下来每行一个正整数 $n$，表示询问的节点数量。
输出格式
输出 $T$ 行，按照询问顺序输出对应的答案。
样例数据
样例 1 输入
5 2 47 1 1 2 3 4 5
样例 1 输出
1 1 2 5 14
样例 1 解释
这是卡特兰数 $C_{n-1}$。
样例 2 输入
10 15 50 11101010101101 1 2 3 4 5 10 100 10000 998244353 1145141919810
样例 2 输出
1 1 3 11 44 27 31 30 10 26
子任务
对于 $100\%$ 的数据范围，保证 $1\le n\le 10^{18}, 2\le K, M\le 50, 1\le T\le 100$。
| 子任务 | 分值 | $n\le $ | $T =$ | 特殊限制 A | 特殊限制 B |
|---|---|---|---|---|---|
| $1$ | $10$ | $100$ | $100 $ | ||
| $2$ | $4$ | $10^4$ | $1$ | $\checkmark$ | |
| $3$ | $6$ | ||||
| $4$ | $30$ | $10^{18}$ | $100$ | $\checkmark$ | $\checkmark$ |
| $5$ | $15$ | ||||
| $6$ | $15 $ | $\checkmark$ | |||
| $7$ | $20$ |
特殊限制 A：$M$ 为质数
特殊限制 B：$\gcd(n,M)=1$