Aruba 和 Ball 又在玩游戏，下面將他們分別簡稱為 A 和 B。

給定一棵 $n$ 個點的有根樹，標號從 $1$ 到 $n$，根的標號是 $1$。每個節點的兒子數只能為 $0$ 或 $2$。將節點分成下列三類：

• ${A}$：到根距離為偶數的所有非葉節點的集合，其中根到自己的距離為 $0$
• ${B}$：到根距離為奇數的所有非葉節點的集合
• ${L}$：葉節點的集合

而對於所有葉子節點 $u\in{L}$，都會被分配一個二元組 $(c(u), d(u))$。其中 $c$ 和 $d$ 可以看成是定義域為 ${L}$ 的函數。

遊戲開始前：

• A 對於 ${A}$ 中的每個點 $u$，從 $u$ 的兩條指向兒子的邊中選擇一條，將其標記為重邊；

• B 對於 ${B}$ 中的每個點 $u$，從 $u$ 的兩條指向兒子的邊中選擇一條，將其標記為重邊。

• 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]$，那麼一共有 $k^{2|{L}|}$ 組不同的 $(c,d)$。 現在要求對每組不同的 $(c, d)$ 都計算納什均衡點的個數。由於 $k^{2|{L}|}$ 過大，所以輸出這 $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$ 的子樹，並以點 $s$ 作為樹根開始遊戲，將上面問題的答案記為 $Ans_s$。

你需要求出所有 $Ans_s\bmod p$。

輸入格式

第一行三個整數 $n,k,p(3\leq n\leq 5000,k\le 10^9,n< p\leq 10^6)$。保證 $n$ 為奇數。

第二行包括 $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

範例 1 輸出

24
4
4

範例 2 輸入

9 2 191981
1 1 3 4 4 3 7 7

範例 2 輸出

8960
4
1152
24
4
4
24
4
4

範例 3 輸入

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

範例 3 輸出

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$。