G - Yet Another RGB Sequence Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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

出力

答えを出力せよ。

入力例 1

2 1 1 1

出力例 1

6

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

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

入力例 2

1000000 1000000 1000000 1000000

出力例 2

80957240

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

Score : 600 points

Problem Statement

You are given integers R, G, B, and K. How many strings S consisting of R, G, and B satisfy all of the conditions below? Find the count modulo 998244353.

  • The number of occurrences of R, G, and B in S are R, G, and B, respectively.
  • The number of occurrences of RG as (contiguous) substrings in S is K.

Constraints

  • 1 \leq R,G,B\leq 10^6
  • 0 \leq K \leq \mathrm{min}(R,G)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

R G B K

Output

Print the answer.

Sample Input 1

2 1 1 1

Sample Output 1

6

The following six strings satisfy the conditions.

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

Sample Input 2

1000000 1000000 1000000 1000000

Sample Output 2

80957240

Find the count modulo 998244353.