3s 512M

题目描述

对于一棵树 $T$，定义 $v(T)$ 为将 $T$ 的顶点染成黑色和白色的方案数，且需满足以下条件：

• 对于树中任意两个黑色顶点 $u, v$，从 $u$ 到 $v$ 的简单路径上的所有顶点都必须为黑色；
• 至少有 $k$ 条无向边 $(u, v)$ 满足 $u$ 和 $v$ 的颜色不同。

对于所有有 $n$ 个标号顶点的无根树 $T$，计算 $\sum v(T)$ 的值，并将结果对 $998244353$ 取模。

输入格式

输入共一行，包含两个正整数 $n, k$（$1 \leq n \leq 10^7$，$1 \leq k \leq 5000$）。

输出格式

输出一个整数，表示答案。

输入输出样例 #1

输入 #1

3 1

输出 #1

15

输入输出样例 #2

输入 #2

6 2

输出 #2

17286

输入输出样例 #3

输入 #3

30 9

输出 #3

434031055

输入输出样例 #4

输入 #4

114514 2520

输出 #4

136362204

说明/提示

在第一个测试用例中，只有 $3$ 种不同的树 $T$，它们都是链形结构，因此每棵树的 $v(T)$ 相同。设 $0$ 表示黑色，$1$ 表示白色，则共有 $5$ 种满足条件的染色方案：

其中，方案 $(1,1,1)$ 与 $(0,0,0)$ 不满足第二个条件（即没有至少 $k=1$ 条黑白相邻的边），而方案 $(0,1,0)$ 不满足第一个条件（两个黑色顶点之间的路径上存在白色顶点）。

因此，最终答案为 $3 \times 5 = 15$。