Problem Statement

For sequences $a$ and $b$, define the sequence $a * b$ by the following recurrence:

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

Here, a "sequence" always means an infinitely long sequence of non-negative integers. For a sequence $a$ and a positive integer $n$, $a_n$ denotes the $n$-th component of $a$, and on the right-hand side of the above formula, $i,j,k$ range over all triples of positive integers satisfying $i+j+k=n$.

For a sequence $a$ and a positive integer $m$, define the sequence $a^m$ by the following recursion:

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

In short, $a^m$ is the $m$-th power of $a$ with respect to $*$, computed in a left-associative manner.

For each positive integer $n$ less than or equal to $N$, find the remainder of $(A^M)_n$ divided by $P$.

Background

Here is the background for those familiar with algebra. A $2$-variable formal power series with $\mathbb{Q}$ coefficients $F(x,y) = \sum_{i,j=0}^{\infty} F_{i,j} x^i y^j$ (where $F_{i,j}$ is a rational number for all non-negative integers $i,j$) satisfying the conditions

1. $F_{0,0} = 0$
2. $F_{1,0} = F_{0,1} = 1$
3. $F(F(x,y),z) = F(x,F(y,z))$ (an equality of $3$-variable formal power series)

is called a formal group law with $\mathbb{Q}$ coefficients. For example, $x+y$ is a formal group law, and as a $2$-variable function on a $\mathbb{Q}$-algebra it coincides with the additive group operation. $x+y+xy$ is also a formal group law, and as a $2$-variable function on $\mathbb{Q}$ it coincides with the expression obtained by expanding the multiplicative group operation on the elements other than $0$ around the identity element $1$. A general formal group law does not necessarily define an operation on a general $\mathbb{Q}$-algebra, but it does define, for example, a group operation on the ideal $x \mathbb{Q}[[x]]$ of the formal power series ring $\mathbb{Q}[[x]]$.

The operation $*$ in this problem is the group operation on $x \mathbb{Q}[[x]]$ defined by the formal group law $\frac{x+y}{1-xy}$ with $\mathbb{Q}$ coefficients, translated into the language of sequences.

Input

The input is given from standard input in $2$ lines in the following format:

• The $1$-st line contains $N, M, P$, separated by single spaces.
• The $2$-nd line contains $A_n$ for each positive integer $n$ less than or equal to $N$, in increasing order of $n$, separated by single spaces.

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

Constraints

The input satisfies the following constraints:

• $N$ is an integer satisfying $1 \leq N \leq 500$.
• $M$ is an integer satisfying $1 \leq M \leq 10^{18}$.
• $P$ is a prime satisfying $N < P < 10^9$.
• For every positive integer $n$ less than or equal to $N$, $A_n$ is an integer satisfying $0 \leq A_n \leq 10^{18}$.

Output

Output the remainder of $(A^M)_n$ divided by $P$ for each positive integer $n$ less than or equal to $N$, in increasing order of $n$, separated by single spaces, on $1$ line.

Print a newline at the end.

Sample

1 1 2
1

1

2 2 3
1 2

2 1

3 3 5
1 1 1

3 3 1