3669: 活动(第四轮03)
题目描述
超市里,有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。