QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 512 MB Total points: 100

# 8670. 独立

统计

给定一棵 $n$ 个节点的树和一个正整数 $m$,每个节点的权值在 $[1,m]$ 中等概率独立随机。

求这棵树的最大独立集的期望乘上 $m^n$ 后的结果。

答案对 $998244353$ 取模。

一棵点权为 $a_{1\dots n}$ 的树的最大独立集为 $\max\limits_{S\subseteq \{1,2,\cdots,n\}} \left(\sum\limits_{i\in S} a_i\right)$,且 $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):无特殊限制。