树异或价值

Problem Description

曾经有一棵 $n$ 个节点的有根树，其根节点的编号为 $1$。同时，小 $\omega$ 有一个大小为 $n$ 的数组 $a_1,a_2,\ldots,a_n$ 。 定义数组 $a$ 的价值为：

$$\sum_{i=1}^n \sum_{j=1}^n (a_i \oplus a_j) \times dep_{\mathrm{LCA}(i,j)} $$

相关定义解释：

• $\oplus$ 表示按位异或。
• $dep_x$ 表示 $x$ 的深度，即 $x$ 到根节点的路径上节点的数量。
• $\mathrm{LCA(i,j)}$ 表示 $i$ 和 $j$ 的最近公共祖先。 不幸的是，很多年之后小 $\omega$ 忘记了数组 $a$。但是他记得：
• $\forall 1 \le i \le n$, $0 \le a_i \le 2^k - 1$，其中 $k$ 是一个给定的常数。
• 在所有 $2^{kn}$ 种可能的 $a$ 数组中，小 $\omega$ 的 $a$ 数组的价值是最大的。 小 $\omega$ 并不满足于找到一个合法的 $a$ 数组，他更想知道有多少种 $a$ 数组能满足上述条件。答案可能很大，请输出其对 $998244353$ 取模的结果。

Input

输入包含多组测试数据。 第一行包含一个整数 $T$ ($1 \le T \le 20$)，表示测试数据的组数。 对于每组测试数据， 第一行包含两个整数 $n$, $k$ ($1 \le n \le 2 \times 10^5, 1 \le k \le 10^9$)，表示树与 $a$ 数组的大小，$a$ 数组元素的上界。 第二行包含 $n-1$ 个整数 $p_2,p_3,\ldots,p_n$ ($1 \le p_i < i$), 其中 $p_i$ 表示树上节点 $i$ 的父亲。

Output

对于每组测试数据，输出一行一个整数，表示合法 $a$ 数组数量对 $998244353$ 取模的结果。

Sample Input

1
3 3
1 1

Sample Output

216

Source

2024“钉耙编程”中国大学生算法设计超级联赛（9）