AT_jsc2023_final_f.Adjacent Binomial Coefficients

给定整数 $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)=\prod_{1 \leq i \leq N-1} {A_i + A_{i+1} \choose A_i }
]

请你求所有好数列对应的 $f(A)$ 的总和，结果对 $998244353$ 取模。

输入从标准输入按以下格式给出。

$N$ $M$ $K$

输出答案。

样例解释 1

好数列有 $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 \leq N \leq 250000$
• $0 \leq K \leq M \leq 250000$
• 所有输入均为整数。

由 ChatGPT 5 翻译