注意：我們區分節點子節點的順序。
帶加強同學人如其名，喜歡加強各種計數題，尤其喜歡多項木。所謂多項木，就是「多項」+「木」，而「木」也有「樹」之含義，也就是用多項式來數樹。
帶加強認為一顆有根樹的穩定程度取決於這棵樹的每個節點有幾個孩子，於是他規定了一個正整數集合 $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$