102666: [AtCoder]ABC266 G - Yet Another RGB Sequence

Problem Statement

You are given integers $R$, $G$, $B$, and $K$. How many strings $S$ consisting of R, G, and B satisfy all of the conditions below? Find the count modulo $998244353$.

• The number of occurrences of R, G, and B in $S$ are $R$, $G$, and $B$, respectively.
• The number of occurrences of RG as (contiguous) substrings in $S$ is $K$.

Constraints

• $1 \leq R,G,B\leq 10^6$
• $0 \leq K \leq \mathrm{min}(R,G)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$R$ $G$ $B$ $K$

Output

Print the answer.

Sample Input 1

2 1 1 1

Sample Output 1

6

The following six strings satisfy the conditions.

• RRGB
• RGRB
• RGBR
• RBRG
• BRRG
• BRGR

Sample Input 2

1000000 1000000 1000000 1000000

Sample Output 2

80957240

Find the count modulo $998244353$.

问题描述

给你四个整数$R$，$G$，$B$和$K$。有多少由R，G和B组成的字符串$S$满足以下所有条件？找到模$998244353$的结果。

• $S$中R，G和B的出现次数分别为$R$，$G$和$B$。
• $S$中作为（连续）子字符串的RG的出现次数为$K$。

约束

• $1 \leq R,G,B\leq 10^6$
• $0 \leq K \leq \mathrm{min}(R,G)$
• 输入中的所有值都是整数。

输入

从标准输入以以下格式给出输入：

$R$ $G$ $B$ $K$

输出

打印答案。

样例输入1

2 1 1 1

样例输出1

6

以下六个字符串满足条件。

• RRGB
• RGRB
• RGBR
• RBRG
• BRRG
• BRGR

样例输入2

1000000 1000000 1000000 1000000

样例输出2

80957240

找到模$998244353$的结果。