#6672. 「XXOI 2019」惠和惠惠和惠惠惠

内存限制:256 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: KingSann

题目描述

惠和惠惠在玩一款叫做惠惠惠的游戏

在你的一个希望直接实现后,你和你的朋友开始玩耍。

考虑你和你的朋友在玩三国杀,一开始你的血量为 0

一共有 n+1 个回合(回合 0 \sim n )。

在每个回合,你可以选择如下操作:

  1. 使用「桃」,下一个回合一开始你的血量加一;
  2. 使用「摸鱼」,下一个回合一开始你的血量不变;
  3. 使用「苦肉计」,下一个回合一开始你的血量减一。

任何一个回合中,如果你的血量小于 0 ,你将会直接输掉比赛。

你的朋友不会影响你的血量,且由于起胡番的设定,他不会赢得比赛。

你的武将有一个锁定技,即如果你在这 n+1 个回合中,恰好血量为 0 k 个回合,那么在第 n+1 个回合结束时(也就是说你只需要指定出 n 个操作),你将直接胜利。

求有多少种不同的操作方法,使得你能靠你的锁定技获得胜利。

输入格式

第一行两个整数 n,k ,表示询问。

输出格式

一行一个整数表示答案,答案模 998244353

样例

样例输入

5 3

样例输出

6

样例解释

一共有如下 6 种本质不同的操作方式:

  1. 摸鱼 桃 摸鱼 摸鱼 苦肉计
  2. 桃 苦肉计 桃 摸鱼 苦肉计
  3. 桃 摸鱼 苦肉计 桃 苦肉计
  4. 桃 摸鱼 摸鱼 苦肉计 摸鱼
  5. 桃 桃 苦肉计 苦肉计 摸鱼
  6. 摸鱼 桃 桃 苦肉计 苦肉计

数据范围与提示

1 \le n,k \le 10^5

希望有能模 10^9+7 的做法

upd: 现在的确可以做到 n,k \le 10^7 在模任意素数意义下了

对于 1 \sim 4 号测试点,保证第 i 个测试点有 n \le 10^{1+i}


bonus time

巨大的样例输入:

10000000 100000

巨大的样例输出:

308901689