题目描述

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

3 2 114514
1 1

24
4
4

9 2 191981
1 1 3 4 4 3 7 7

8960
4
1152
24
4
4
24
4
4

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