树异或价值

曾经有一棵 $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$ 取模的结果。

输入包含多组测试数据。

第一行包含一个整数 $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$ 的父亲。

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

1
3 3
1 1

216

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