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

「XXOI 2019」惠和惠惠和惠惠惠

题目描述

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

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

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

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

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

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

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

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

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

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

输入格式

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

输出格式

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

样例

5 3
6

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

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

数据范围与提示

1n,k1051 \le n,k \le 10^5

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

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

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


bonus time

巨大的样例输入:

10000000 100000

巨大的样例输出:

308901689