r.i.p

时间限制：1000 ms　内存限制：512 MiB 评测机器较慢，时限改为2000ms

题目描述

老师给了小智一张纸，上面画着一棵有 $n$ 个节点的树。老师还给了小智 $m$ 支彩色笔，每支笔的颜色都是不同的。老师想要让小智用这 $m$ 种颜色给树的节点涂色，使得这棵树满足如下约束：

• 每个节点都被涂上了这 $m$ 个颜色之一的一种颜色。

• 相邻两个节点（若存在一条边直接连接 $u$ 和 $v$，则我们称 $u,v$ 相邻）的颜色是不同的。

• 任何一种颜色被使用的次数都不能超过 $\lfloor\frac{n}{3}\rfloor + 1$。

需要指出的是，虽然每个节点都必须被涂上一种颜色，但是每个颜色并不必须被使用。

如此简单的任务难不倒小智，所以小智提出了一个更困难的问题：他想知道一共有多少种染色的方案满足老师的要求。小智不会解答这个问题，所以来求助你，请你帮他解决他的问题。

因为方案数可能非常大，你只需要输出这个方案数除以 $998244353$ 的余数。两种染色方案不同当且仅当存在一个节点 $u$，使得 $u$ 在两种方案中被染上的颜色不同。

输入格式

第一行是两个整数，依次表示树的节点数 $n$ 和颜色的个数 $m$。

接下来 $(n - 1)$ 行，每行两个整数 $u, v$，表示树上有一条连接 $u, v$ 的边。

输出格式

输出一行一个整数，表示方案数除以 $998244353$ 的余数。

样例

输入 #1

4 4
1 2
1 3
3 4

输出 #1

108

输入 #2

3 3
1 2
1 3

输出 #2

12

输入 #3

5 5
1 2
1 3
2 4
3 5

输出 #3

1200

输入 #4

5 5
1 2
1 3
2 4
2 5

输出 #4

1140

输入 #5

7 8
1 2
1 3
2 4
2 5
3 6
3 7

输出 #5

929376

输入 #6

6 6
1 2
1 3
3 4
4 5
3 6

输出 #6

18750

输入 #7

10 20
1 2
1 3
2 4
2 5
2 6
2 7
3 8
5 9
9 10

输出 #7

688946281

说明/提示

数据规模与约定

对于全部的测试点，保证 $1 \leq u, v \leq n \leq 120$，$n \leq m \leq 10^6$，保证给出的是一棵树。

提示

请注意常数因子对程序效率造成的影响。