配点 : 500 点
問題文
N 个格子横向排列。从左边开始 i 第几格是格子 i 我们称之为。起初,所有的格子都被涂成白色。
青蛙目前在格子 1 上,并重复以下动作,试图到达格子 N 。
- 将青蛙所在的格子称为 i ,跳到格子 i+1, i+2, \ldots, i+K 中的任意一个。但不能移动到不存在的格子或被涂成黑色的格子。
那么,听到这个的调皮蝌蚪决定将除了格子以外的几个格子涂成黑色。 1, N 我决定把除了几个以外的格子涂成黑色。
可以考虑的黑色格子选择方法有 2^{N-2} 种,但是对于所有这些方法,要计算青蛙到达格子的移动方式的数量,并且其总和 N 求到达的方法数,并求其总和 998244353 后的余数。
制約
- 2 \leq N \leq 3 \times 10^5
- 1 \leq K \leq N-1
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N K
出力
计算出的总和为 998244353 后的余数 在 1 行输出。
入力例 1
4 2
出力例 1
5
蝌蚪会将格子中的几个格子涂成黑色。 2, 3 将其中的一些方格涂黑。
- 质量 从 2 是白色且格子 3 也是白色的情况下,青蛙有 1 \rightarrow 2 \rightarrow 3 \rightarrow 4, 1 \rightarrow 2 \rightarrow 4, 1 \rightarrow 3 \rightarrow 4 可以得到第 3 种移动方式。
- 质量 从 2 是白色且格子 3 是黑色的情况下,青蛙有 1 \rightarrow 2 \rightarrow 4 可以得到第 1 种移动方式。
- 质量 从 2 是黑色且格子 3 是白色的情况下,青蛙有 1 \rightarrow 3 \rightarrow 4 可以得到第 1 种移动方式。
- 质量 从 2 是黑色且格子 3 也是黑色的情况下,青蛙到格子 4 无法到达。
答案是 不超过 3 + 1 + 1 + 0 = 5 。
入力例 2
6 1
出力例 2
1
青蛙 1 只能每次移动一格,所以即使有一格被小蝌蚪涂成黑色,也会卡住。 N 无法到达。
入力例 3
64 26
出力例 3
677439847
998244353 后的余数。
原案: 夏美曾严