题目描述

给定整数 $R$、$G$、$B$ 和 $K$，求满足以下所有条件的字符串 $S$ 的个数。结果对 $998244353$ 取模。

• 字符串 $S$ 仅由字符 R、G 和 B 组成，且 R、G、B 在 $S$ 中的出现次数分别为 $R$、$G$、$B$。
• 在 $S$ 中，RG 作为连续子字符串出现的次数恰好为 $K$。

输入格式

第一行输入四个整数 $R$ $G$ $B$ $K$

输出格式

输出一个整数代表答案

2 1 1 1

6

1000000 1000000 1000000 1000000

80957240

提示

数据范围

• $1\ \leq\ R,G,B\leq\ 10^6$
• $0\ \leq\ K\ \leq\ \mathrm{min}(R,G)$

样例 1 解释

满足条件的有 $6$ 个

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