#222. 方格填数

方格填数

无额外样例。

题目描述

NN 个方格排成一排,让你往方格中填数。每个方格只能填 0 或 1,不能不填,要求:

  • 任意两个 1 之间至少要有 KK 个 0。(如果填写的 1 的总个数少于两个,则无此要求。)

问:你有多少种不同的填法?答案可能很大,你需要将答案 modmod 998244353998244353 后输出。

两种填法不同,当前仅当至少存在一个格子在两种填法中所填的数字不同。

输入

一行,包含两个整数 N,KN, K

输出

一个整数,表示答案 modmod 998244353998244353

样例1输入

3 1

样例1输出

5

样例1解释

5 种填法分别为:000、001、010、100、101

样例2输入

1234567 8910

样例2输出

142844805

数据范围

1≤N,K≤1071 ≤ N, K ≤ 10^7