题目描述

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