题目描述

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) ) 如果满足以下条件，那么该组策略是一个纳什均衡点：

1. 在 A 的策略不改变的情况下，B 无法通过改变自己的策略获得更高分。即在策略 ( (f, g') ) 中 B 的得分总小于等于 ( (f,g) ) 中 B 的得分。
2. 在 B 的策略不改变的情况下，A 无法通过改变自己的策略获得更高分。即在策略 ( (f', g) ) 中 A 的得分总小于等于 ( (f,g) ) 中 A 的得分。

给定树形态和 ( k )。令 ( c ) 和 ( d ) 的值域是 ( \mathbb{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 \leq 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

输出：

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 pts）：( n = 99, k \leq 100 )，( p ) 是质数。
• Subtask 2（30 pts）：( n = 99 )。
• Subtask 3（50 pts）：( n = 4999 )。