题目描述

给定整数 $N, M, X, Y$。

请计算满足以下所有条件的数列 $A=(a_1,\ldots,a_N),\ B=(b_1,\ldots,b_N)$ 的组数，并输出其对 $998244353$ 取模的结果。

• $A$ 是一个非负整数数列。
• $B$ 是 $(0,1,\ldots,M-1)$ 的一个子序列。
• $\sum\limits_{i=1}^{N} a_i = X$。
• $\sum\limits_{i=1}^{N} a_i b_i = Y$。

输入格式

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

$N$ $M$ $X$ $Y$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 4 3 4

输出 #1

5

输入输出样例 #2

输入 #2

1 1 1 1

输出 #2

0

输入输出样例 #3

输入 #3

12345 67890 9876 54321

输出 #3

150392014

说明/提示

限制条件

• $1 \leq N \leq M \leq 2 \times 10^5$
• $1 \leq X, Y \leq 2 \times 10^5$
• 输入均为整数

样例解释 1

满足条件的 $(A,B)$ 组有以下 $5$ 个：

• $A=(0,2,1),\ B=(0,1,2)$
• $A=(1,0,2),\ B=(0,1,2)$
• $A=(1,1,1),\ B=(0,1,3)$
• $A=(1,2,0),\ B=(0,2,3)$
• $A=(2,1,0),\ B=(1,2,3)$

样例解释 2

不存在满足条件的 $(A,B)$ 组。

样例解释 3

请输出对 $998244353$ 取模的结果。

由 ChatGPT 4.1 翻译