配点 : 1200 点
問題文
整数 N,M,K 。
长度为 N 的非负整数序列 A=(A_1,A_2,\cdots,A_N) 满足以下两个条件:良好的数列 对于。
- \sum_{1 \leq i \leq N}A_i=M
- A_1=K
良好的数列 对于 A , 定义f(A) 如下。
\[ f(A)=\prod_{1 \leq i \leq N-1} {A_i+A_{i+1} \选择 A_i } \]
对于所有好的序列 f(A) 的总和 除以 998244353 求余数。
制約
- 2 \leq N \leq 250000
- 0 \leq K \leq M \leq 250000
- 所有输入值都是整数。
入力
输入将以以下格式从标准输入提供。
N M K
出力
输出答案。
入力例 1
3 2 1
出力例 1
3
一个好的序列是 2 有办法,对应 f(A) 的值如下。
-
A=(1,0,1): f(A)={1 \choose 1} \times {1 \choose 0}=1
-
A=(1,1,0): f(A)={2 \choose 1} \times {1 \choose 1}=2
因此,答案是 1+2=3 。 定义
入力例 2
5 10 3
出力例 2
27670
入力例 3
100 0 0
出力例 3
1
入力例 4
100 1000 10
出力例 4
75806874