Aruba and Ball are playing a game again; let us refer to them as A and B, respectively.

Given a rooted tree with $n$ nodes, labeled from $1$ to $n$, where the root is $1$. Each node has either $0$ or $2$ children. We categorize the nodes into the following three types:

• ${A}$: The set of all non-leaf nodes at an even distance from the root, where the distance from the root to itself is $0$.
• ${B}$: The set of all non-leaf nodes at an odd distance from the root.
• ${L}$: The set of all leaf nodes.

For every leaf node $u \in {L}$, a pair $(c(u), d(u))$ is assigned. Here, $c$ and $d$ can be viewed as functions with domain ${L}$.

Before the game begins:

• For each node $u \in {A}$, A chooses one of the two edges pointing to its children and marks it as a heavy edge.

• For each node $u \in {B}$, B chooses one of the two edges pointing to its children and marks it as a heavy edge.

• A's choices can be viewed as a mapping function $f$ with domain ${A}$.

• B's choices can be viewed as a mapping function $g$ with domain ${B}$.

An ordered pair $(f, g)$ is called a strategy profile. It can be seen that A has $2^{|{A}|}$ different choices, and B has $2^{|{B}|}$ different choices. Thus, there are $2^{|{A}|+|{B}|}$ different strategy profiles in total.

Once a strategy profile is determined, starting from the root, one follows the heavy edges downward until reaching a leaf node $u$. At this point, A's score is $c(u)$ and B's score is $d(u)$. A strategy profile $(f, g)$ is a Nash equilibrium if the following conditions are met:

• Given A's strategy $f$, B cannot obtain a higher score by changing their own strategy. That is, for any strategy $(f, g')$, B's score is always less than or equal to B's score in $(f, g)$.
• Given B's strategy $g$, A cannot obtain a higher score by changing their own strategy. That is, for any strategy $(f', g)$, A's score is always less than or equal to A's score in $(f, g)$.

Given the tree structure and $k$. Let the codomain of $c$ and $d$ be ${Z} \cap [1, k]$, so there are $k^{2|{L}|}$ different pairs of $(c, d)$. We are required to calculate the number of Nash equilibria for each distinct pair $(c, d)$. Since $k^{2|{L}|}$ is too large, we output the sum of these $k^{2|{L}|}$ answers. This sum may also be very large, so we output the sum modulo $p$. That is, calculate:

$$\left(\sum_{c\in{{L}\to[k]}}\sum_{d\in{{L}\to[k]}}F(c,d)\right)\bmod p$$

where ${L}\to[k]$ is the set of all functions with domain ${L}$ and codomain $[k]=\{1,2,\dots,k\}$, and $F(c, d)$ is the number of Nash equilibria given $c$ and $d$.

A and B feel that this tree is too large and wish to consider only a subtree. Specifically, for each node $s$, delete the rest of the tree, keep only the subtree rooted at $s$, and start the game with $s$ as the root. Let the answer to the problem above for this subtree be $Ans_s$.

You need to calculate $Ans_s \bmod p$ for all $s$.

Input

The first line contains three integers $n, k, p$ ($3 \leq n \leq 5000, k \leq 10^9, n < p \leq 10^6$). It is guaranteed that $n$ is odd.

The second line contains $n-1$ integers $fa_2, fa_3, \dots, fa_n$. $fa_i$ denotes the parent of $i$, where $1 \leq fa_i < i$.

Output

Output $n$ lines, each containing one integer. The $i$-th line should contain $Ans_i \bmod p$.

Examples

Input 1

3 2 114514
1 1

Output 1

24
4
4

Input 2

9 2 191981
1 1 3 4 4 3 7 7

Output 2

8960
4
1152
24
4
4
24
4
4

Input 3

11 45 233
1 1 3 3 5 5 4 4 9 9

Output 3

80
161
177
150
80
161
161
161
80
161
161

Subtasks

• Subtask $1(20\,\mathrm{pts})$: $n=99, k \leq 100$, $p$ is a prime.
• Subtask $2(30\,\mathrm{pts})$: $n=99$.
• Subtask $3(50\,\mathrm{pts})$: $n=4999$.