8332: 树异或价值

曾经有一棵 $n$ 个节点的有根树，其根节点的编号为 $1$。同时，小 $\omega$ 有一个大小为 $n$ 的数组 a1,a2,…,ana1,a2,…,an 。

定义数组 $a$ 的价值为：

                                                                                                             nn

∑∑(ai⊕aj)×depLCA(i,j)

                                                                                                               i=1j=1

相关定义解释：

• $\oplus$ 表示按位异或。
  
• depxdepx 表示 $x$ 的深度，即 $x$ 到根节点的路径上节点的数量。
  
• $\mathrm{LCA}(\mathrm{i},\mathrm{j})$ 表示 $i$ 和 $j$ 的最近公共祖先。
  

不幸的是，很多年之后小 $\omega$ 忘记了数组 $a$。但是他记得：

• $\forall 1\le i\le n$, 0≤ai≤2k−10≤ai≤2k−1，其中 $k$ 是一个给定的常数。
  
• 在所有 2kn2kn 种可能的 $a$ 数组中，小 $\omega$ 的 $a$ 数组的价值是最大的。
  

小 $\omega$ 并不满足于找到一个合法的 $a$ 数组，他更想知道有多少种 $a$ 数组能满足上述条件。答案可能很大，请输出其对 $998244353$ 取模的结果。

	1
3 3
1 1 

216