又一个 RGB 序列

题目描述

给定整数 $R$、$G$、$B$、$K$。求满足以下所有条件的、由 R、G、B 组成的字符串 $S$ 的个数。答案对 $998244353$ 取模。

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

输入格式

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

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

输出格式

输出答案。

样例

2 1 1 1

6

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

RRGB

RGRB

RGBR

RBRG

BRRG

BRGR

1000000 1000000 1000000 1000000

80957240

数据范围

• $1 \le R,G,B \le 10^6$
• $0 \le K \le \min(R,G)$
• 输入中的所有值均为整数