题目背景

传智杯 2021 决赛 G 题。

题目描述

传智专修学院的老师给小智布置了一项任务。

老师给了小智一张纸，上面画着一棵有 $n$ 个节点的树（如果你不知道什么是树，可以参考上一题对此的解释）。老师还给了小智 $m$ 支彩色笔，每支笔的颜色都是不同的。老师想要让小智用这 $m$ 种颜色给树的节点涂色，使得这棵树满足如下约束：

1. 每个节点都被涂上了这 $m$ 个颜色之一的一种颜色。
2. 相邻两个节点（若存在一条边直接连接 $u$ 和 $v$，则我们称 $u,v$ 相邻）的颜色是不同的。
3. 任何一种颜色被使用的次数都不能超过 $\lfloor\frac{n}{3}\rfloor + 1$。

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

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

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

输入格式

第一行是两个整数，依次表示树的节点数 $n$ 和颜色的个数 $m$。
接下来 $(n - 1)$ 行，每行两个整数 $u, v$，表示树上有一条连接 $u, v$ 的边。

输出格式

输出一行一个整数，表示方案数除以 $998,244,353$ 的余数。

4 4
1 2
1 3
3 4

108

3 3
1 2
1 3

12

5 5
1 2
1 3
2 4
3 5

1200

5 5
1 2
1 3
2 4
2 5

1140

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

929376

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

18750

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

688946281

提示

数据规模与约定

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

提示

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