给定一个整数 $$$k$$$ 和一棵由 $$$n$$$ 个顶点组成的无向树。
某对顶点之间的简单路径(每个顶点最多出现一次的路径)的长度是该路径中的边数。树的直径是该树的所有顶点对之间的简单路径的最大长度。
您即将从树中删除一组边。当边缘被移除时,树会分裂成多个较小的树。如果所有生成的树的直径小于或等于 $$$k$$$,则该边集有效。
如果有一条边仅出现在其中一组边中,则两组边是不同的。
计算有效边集的数量,以 $$$998\,244\,353$$$ 为模。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 5000$$$, $$$0 \le k \le n - 1$$$) - 分别是树的顶点数和最大允许直径。
接下来的 $$$n-1$$$ 行中的每一行都包含一条边的描述:两个整数 $$$v$$$ 和 $$$u$$$ ($$$1 \le v, u \le n$$$, $$$v \neq u$$$)。
给定的边形成一棵树。
输出
打印单个整数 - 有效边集的数量以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
4 3 1 2 1 3 1 4
输出 #1
8
输入 #2
2 0 1 2
输出 #2
1
输入 #3
6 2 1 6 2 4 2 6 3 6 5 6
输出 #3
25
输入#4
6 3 1 2 1 5 2 3 3 4 5 6
输出#4
29
注意
在第一个示例中,给定树的直径已经小于或等于 $$$k$$$。因此,您可以选择任何一组要删除的边,生成的树的直径将小于或等于 $$$k$$$。有 $$$2^3$$$ 套,包括空的一套。
在第二个示例中,您必须删除唯一的边。否则,直径将为 $$$1$$$,大于 $$$0$$$。
这是第三个和第四个示例的树: