配点 : $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 \mathrm{min}(R,G)$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

答えを出力せよ。

2 1 1 1

6

条件を満たす文字列は以下の $6$ 個です。

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

1000000 1000000 1000000 1000000

80957240

個数を $998244353$ で割った余りを求めてください。