問題文

各数列 $a$ と $b$ に対し、数列 $a * b$ を次の漸化式で定めます：

$\displaystyle (a * b)_n = a_n + b_n + \sum_{i+j+k=n} a_i b_j (a * b)_k $

ただしここでは数列と言ったら長さが無限である非負整数列を指し、各数列 $a$ と正整数 $n$ に対し $a_n$ で $a$ の $n$ 個目の成分を表し、上式右辺において $i,j,k$ は $i+j+k=n$ を満たす正整数の組全体をわたります。

各数列 $a$ と正整数 $m$ に対し、数列 $a^m$ を以下の再帰式で定めます：

$\displaystyle a^m = \left\{ \begin{array}{ll} a & (m = 1) \\ a^{m-1} * a & (m > 1) \end{array} \right. $

要するに $a^m$ は $*$ に関する $a$ の $m$ 乗を左結合的に計算したものです。

$N$ 以下の各正整数 $n$ に対する $(A^M)_n$ を $P$ で割った余りを求めてください。

背景

代数を知っている人向けに背景を説明します。$\mathbb{Q}$ 係数 $2$ 変数形式冪級数 $F(x,y) = \sum_{i,j=0}^{\infty} F_{i,j} x^i y^j$（任意の非負整数 $i,j$ に対し $F_{i,j}$ は有理数）であって、条件

1. $F_{0,0} = 0$
2. $F_{1,0} = F_{0,1} = 1$
3. $F(F(x,y),z) = F(x,F(y,z))$（$3$ 変数形式冪級数の等式）

を満たすものを $\mathbb{Q}$ 係数の形式群法則と呼びます。例えば $x+y$ は形式群法則であり、$\mathbb{Q}$ 代数上の $2$ 変数関数としては加法群演算と一致します。$x+y+xy$ も形式群法則であり、$\mathbb{Q}$ 上の $2$ 変数関数としては $0$ でない元の乗法群演算を単位元 $1$ 中心に展開した式と一致します。一般の形式群法則は必ずしも一般の $\mathbb{Q}$ 代数上の演算を定めませんが、例えば形式冪級数環 $\mathbb{Q}[[x]]$ のイデアル $x \mathbb{Q}[[x]]$ 上の群演算を定めます。

この問題における $*$ 演算は、$\mathbb{Q}$ 係数の形式群法則 $\frac{x+y}{1-xy}$ が定める $x \mathbb{Q}[[x]]$ 上の群演算を数列の言葉に翻訳したものです。

入力

入力は以下の形式で標準入力から $2$ 行で与えられます：

• $1$ 行目に $N, M, P$ が半角空白区切りで与えられます。
• $2$ 行目に $N$ 以下の各正整数 $n$ に対する $A_n$ が $n$ の小さい順に半角空白区切りで与えられます。

$N$ $M$ $P$
$A_1$ $\cdots$ $A_N$

制約

入力は以下の制約を満たします：

• $N$ は $1 \leq N \leq 500$ を満たす整数である。
• $M$ は $1 \leq M \leq 10^{18}$ を満たす整数である。
• $P$ は $N < P < 10^9$ を満たす素数である。
• $N$ 以下の任意の正整数 $n$ に対し、$A_n$ は $0 \leq A_n \leq 10^{18}$ を満たす整数である。

出力

$N$ 以下の各正整数 $n$ に対する $(A^M)_n$ を $P$ で割った余りを $n$ の小さい順に半角空白区切りで $1$ 行に出力してください。

最後に改行してください。

サンプル

1 1 2
1

1

2 2 3
1 2

2 1

3 3 5
1 1 1

3 3 1