Aruba と Ball がゲームをしています。以下、彼らをそれぞれ A と B と呼びます。

$n$ 個の頂点を持つ根付き木が与えられます。頂点には $1$ から $n$ までの番号が振られており、根の番号は $1$ です。各頂点の子の数は $0$ または $2$ です。頂点を以下の3つの集合に分類します。

• ${A}$：根からの距離が偶数であるすべての非葉頂点の集合（根から自分自身への距離は $0$ とする）
• ${B}$：根からの距離が奇数であるすべての非葉頂点の集合
• ${L}$：葉頂点の集合

すべての葉頂点 $u\in{L}$ には、二元組 $(c(u), d(u))$ が割り当てられます。ここで $c$ と $d$ は ${L}$ を定義域とする関数とみなせます。

ゲーム開始前：

• A は ${A}$ に属する各頂点 $u$ について、その $2$ つの子へ向かう辺のうち $1$ つを選び、重辺としてマークします。

• B は ${B}$ に属する各頂点 $u$ について、その $2$ つの子へ向かう辺のうち $1$ つを選び、重辺としてマークします。

• A の選択は ${A}$ を定義域とする写像 $f$ とみなせます。

• B の選択は ${B}$ を定義域とする写像 $g$ とみなせます。

このとき、順序対 $(f,g)$ を戦略の組と呼びます。A には $2^{|{A}|}$ 通り、B には $2^{|{B}|}$ 通りの選択肢があるため、戦略の組は合計で $2^{|{A}|+|{B}|}$ 通り存在します。

戦略が決定されると、根から開始して重辺を辿り続け、ある葉頂点 $u$ に到達します。このとき、A のスコアは $c(u)$、B のスコアは $d(u)$ となります。戦略の組 $(f, g)$ が以下の条件を満たすとき、その戦略の組はナッシュ均衡点であると言います。

• A の戦略を固定したとき、B は自身の戦略を変更してもこれより高いスコアを得ることができない。すなわち、任意の戦略 $(f, g')$ に対して、B のスコアは $(f, g)$ における B のスコア以下である。
• B の戦略を固定したとき、A は自身の戦略を変更してもこれより高いスコアを得ることができない。すなわち、任意の戦略 $(f', g)$ に対して、A のスコアは $(f, g)$ における A のスコア以下である。

木の形状と $k$ が与えられます。$c$ と $d$ の値域を ${Z}\cap[1,k]$ とすると、$(c,d)$ の組み合わせは合計で $k^{2|{L}|}$ 通り存在します。 すべての $(c, d)$ の組に対してナッシュ均衡点の個数を計算してください。$k^{2|{L}|}$ は非常に大きいため、これらすべてのケースにおけるナッシュ均衡点の個数の総和を求めます。この総和も非常に大きくなる可能性があるため、$p$ を法とした値を求めてください。すなわち、以下を計算します。

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

ここで ${L}\to[k]$ は定義域が ${L}$、値域が $[k]=\{1,2,\dots,k\}$ であるすべての関数の集合であり、$F(c, d)$ は与えられた $c, d$ におけるナッシュ均衡点の個数です。

A と B はこの木が大きすぎると考え、部分木のみを考えることにしました。具体的には、各頂点 $s$ に対して、その頂点 $s$ を根とする部分木のみを残してゲームを行った場合の答えを $Ans_s$ とします。

すべての $Ans_s\bmod p$ を求めてください。

入力

1行目に3つの整数 $n, k, p$ が与えられます ($3\leq n\leq 5000, k\le 10^9, n< p\leq 10^6$)。$n$ は奇数であることが保証されます。

2行目に $n-1$ 個の整数 $fa_2, fa_3, \dots, fa_n$ が与えられます。$fa_i$ は $i$ の親を表し、$1\leq fa_i < i$ を満たします。

出力

$n$ 行出力してください。$i$ 行目には $Ans_i\bmod p$ を出力してください。

入出力例

入出力例 1

入力

3 2 114514
1 1

出力

24
4
4

入出力例 2

入力

9 2 191981
1 1 3 4 4 3 7 7

出力

8960
4
1152
24
4
4
24
4
4

入出力例 3

入力

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

出力

80
161
177
150
80
161
161
161
80
161
161

小課題

• Subtask $1(20\,\mathrm{pts})$：$n=99, k\leq 100$、$p$ は素数。
• Subtask $2(30\,\mathrm{pts})$：$n=99$。
• Subtask $3(50\,\mathrm{pts})$：$n=4999$。