注：ノードの子供の順序は区別します。

Daiqiang君はその名の通り、様々な計数問題を強化することを好んでおり、特に「多項木（Polynomial Tree）」を好んでいます。多項木とは「多項」と「木」を組み合わせたもので、多項式を用いて木を数え上げることを意味します。

Daiqiang君は、根付き木の安定度は各ノードが持つ子供の数に依存すると考えています。そこで、正整数の集合 $D$ を定め、ある根付き木が「鉄」であるとは、その木のすべての非葉ノードについて、その子供の数を $x$ としたときに $x \in D$ が成り立つことであると定義しました。

Daiqiang君は毎回 $n$ を問いかけてきます。$n$ 個の葉を持つ「鉄」な根付き木がいくつあるか、答えを $M$ で割った余りを求めてください。

入力

1行目に3つの正整数 $T, K, M$ が与えられます。それぞれクエリの回数、集合 $D$ の範囲、法を表します。

続く1行に長さ $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

注記

これはカタラン数 $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$ を満たします。

特殊制限 A：$M$ は素数

特殊制限 B：$\gcd(n,M)=1$