分数: 1800 点
问题陈述
给你正整数 N 和 K。考虑一棵无向树 T 与 (2K + 1)N + 1 顶点标记自 1 to (2K + 1)N + 1。在所有这样的树中,找到数字,模 998244353,满足以下条件的树。
- 可以删除所有边缘 T 通过重复以下操作:
- 选择长度的路径 2K + 1 并删除其中的所有边缘。
正式地,选择一系列不同的顶点 v_0, v_1, \dots, v_{2K+1} 使得存在边缘 (v_i, v_{i+1}) 对于所有人 i 这样 0 \leq i \leq 2K,并删除边缘 (v_i, v_{i+1}) 对于所有人 i 这样 0 \leq i \leq 2K.
- 选择长度的路径 2K + 1 并删除其中的所有边缘。
约束
- 1 \leq N \leq 1.3 \times 10^5
- 1 \leq K \leq 50
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K
输出
打印数字,模数 998244353,树木 (2K + 1)N + 1 满足条件的顶点。
示例输入 1
2 1
示例输出 1
8820
例如,考虑一棵有边的树 (1, 2), (2, 3), (2, 4), (2, 6), (3, 7),和 (4, 5)。通过执行以下步骤,可以删除树中的所有边,从而满足问题陈述中的条件:
- 选择路径 (1,2,4,5) 并删除边缘 (1,2), (2,4), (4,5).
- 选择路径 (6,2,3,7) 并删除边缘 (6,2), (2,3), (3,7).

有 8820 这样的树一共有。
示例输入 2
70 1
示例输出 2
273892456
记住打印计数模数 998244353.
示例输入 3
12 29
示例输出 3
898069699
示例输入 4
100000 50
示例输出 4
158600909