3669: 活动(第四轮03)

内存限制:256 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:1 解决:1

题目描述

超市里,有n种物品,第i种物品的重量为i,且每种物品都有无限多个。

有一天,超市举办了一个活动。活动的规则是:首先你从盒子里抽取一个数字 x 你有一个空篮子,初始时篮子内物品总重量为 0。你每次可以将一个物品放入篮子,但假设当前篮子内物品总重量为w,则只能选择重量≥ w的物品放进篮子。你可以按照规则放多次,但不能把已经在篮子里的物品取出篮子。如果你可以按照规则,使得篮子内物品的总重量刚好为x,则超市就赠送你一个小礼品。

牛牛发现了这个活动的一个必胜策略,他参加了很多次活动,导致超市面临亏损。于是在牛牛打算再次参与活动时,超市老板对牛牛提出挑战,如果牛牛可以不使用第y种物品的前提下,仍然使篮子内物品的总重量刚好为x,则超市老板就赠送牛牛一份大礼品,否则牛牛将再也不许参加活动。

牛牛欣然接受,他只是觉得无聊。于是他打算考考你,在不使用第y种物品的前提下,他可以有多少种合法的放物品方案,使得篮子内物品的总重量刚好为x 两种方案不同当且仅当牛牛在两种方案中篮子内物品的数量不同,或者两种方案中第k次放到篮子的物品种类不同。

由于方案数可能很大,他只需要你输出方案数除以998244353的余数就可以啦。

输入

第一行,三个正整数n, x, y ,以空格相隔。

输出

一行,一个整数,表示方案数除以 998244353 的余数。

样例输入 复制

5 7 3

样例输出 复制

3

提示

【样例 1 输入】

5 7 3

【样例 1 输出】

3

【样例 1 说明】

3 种方案分别是:

(1) 放入 1, 放入 1, 放入 5

(2) 放入 1, 放入 2, 放入 4

(3) 放入 2, 放入 5。

【样例 2 输入】

8 15 4

【样例 2 输出】

4

【样例 3 输入】

12345 4321 24

【样例 3 输出】

795333476

【数据范围】

对于 10数据,满足1 n, x 10。对于 40数据,满足1 n, x 1000。

对于 100数据,满足1 ≤ n, x ≤ 100000,1 ≤ y ≤ n。


来源/分类