G - 又一个RGB序列

得分 : $600$ 分

问题描述

给定整数 $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 \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$ 取模。