给你一棵有 $$$n$$$ 个顶点的树。您将选择 $$$k$$$ (不一定不同)简单路径,以便可以将树的所有边分为三组:不包含在任何路径中的边、恰好属于这些路径之一的边、以及属于所有选定路径的部分的边,并且后一组应该是非空的。
计算以 $$$998244353$$$ 为模选择 $$$k$$$ 路径的方式数。
路径被枚举,换句话说,如果存在这样的 $$$i$$$ ($$$1 \leq i \leq k$$$) 和第 $$$i$$$ 路径在一种方式中包含该边而在另一种方式中不包含它的边,则认为两种方式是不同的。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n, k \leq 10^{5}$$$) - 树中的顶点数和所需的路径数。
接下来的 $$$n - 1$$$ 行描述树的边缘。每行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le n$$$, $$$a \ne b$$$) — 边的端点。保证给定的边形成一棵树。
输出
打印选择 $$$k$$$ 的方法数量,枚举不一定是不同的简单路径,对于每条边,要么不包含在任何路径中,要么只包含在一个路径中,要么包含在所有 $$$k$$$ 路径中,并且所有路径的交集非空。
由于答案可能很大,请打印 $$$998244353$$$ 的模。
示例
输入 #1
3 2 1 2 2 3
输出 #1
7
输入 #2
5 1 4 1 2 3 4 5 2 1
输出 #2
10
输入 #3
29 29 1 2 1 3 1 4 1 5 5 6 5 7 5 8 8 9 8 10 8 11 11 12 11 13 11 14 14 15 14 16 14 17 17 18 17 19 17 20 20 21 20 22 20 23 23 24 23 25 23 26 26 27 26 28 26 29
输出 #3
125580756
注意
在第一个示例中,以下方式是有效的:
- $$$((1,2), (1,2))$$$,
- $$$((1,2), (1,3))$$$,
- $$$((1,3), (1,2))$$$,
- $$$((1,3), (1,3))$$$,
- $$$((1,3), (2,3))$$$,
- $$$((2,3), (1,3))$$$,
- $$$((2,3), (2,3))$$$.
在第二个示例中 $$$k=1$$$,因此所有 $$$n \cdot (n - 1) / 2 = 5 \cdot 4 / 2 = 10$$$ 路径都是有效的。
在第三个例子中,答案是$$$\geq 998244353$$$,所以它是对$$$998244353$$$取模,不要忘记!