给定一棵 n 个节点的树和一个正整数 m,每个节点的权值在 [1,m] 中等概率独立随机。
求这棵树的最大独立集的期望乘上 mn 后的结果。
答案对 998244353 取模。
一棵点权为 a1…n 的树的最大独立集为 max,且 S 还需满足其中的任意两个点之间不存在边直接连接两者。
Input
第一行两个正整数 n,m。
接下来 n-1 行,每行两个正整数,表示树的一条边。
Output
一行一个非负整数,表示答案。
Example
Input
3 2 1 2 1 3
Output
24
Explanation
比如当点权为 [2,1,1] 时,最大独立集为 2,选择 \{1\} 或者 \{2,3\} 均可。
Scoring
对于全部的数据,满足 1\le n\le 2000,1\le m\le 10^8。
- Subtask1(11pts):n,m\le 5。
- Subtask2(24pts):n,m\le 20。
- Subtask3(13pts):n,m\le 500。
- Subtask4(27pts):n\le 500。
- Subtask5(25pts):无特殊限制。