← 返回题目列表

AtCoder · jsc2023_final_f

F. 相邻二项式系数

中文机器翻译题面 查看原题

配点 : 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