D - Yet Another ABC String 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 1000 点

問題文

整数 A,B,C が与えられます． A, B, C からなる文字列 S であって，以下の条件をすべて満たすものの個数を 998244353 で割った余りを求めてください．

  • S に含まれる A, B, C の個数はそれぞれ A,B,C 個である．
  • S は（連続する）部分文字列として，ABC, BCA, CAB のいずれも含まない．

制約

  • 1 \leq A,B,C \leq 10^6
  • 入力される値はすべて整数である

入力

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

A B C

出力

答えを出力せよ．

入力例 1

1 1 1

出力例 1

3

条件を満たす文字列は，ACB, CBA, BAC の 3 つです．

入力例 2

2 2 2

出力例 2

42

入力例 3

96 11 46

出力例 3

818015722

入力例 4

125132 102271 152064

出力例 4

128086069

Score : 1000 points

Problem Statement

You are given integers A, B, and C. How many strings S consisting of A, B, and C satisfy all of the following conditions? Find the count modulo 998244353.

  • The number of occurrences of A, B, and C in S are A, B, and C, respectively.
  • S contains none of ABC, BCA, and CAB as a (contiguous) substring.

Constraints

  • 1 \leq A,B,C \leq 10^6
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C

Output

Print the answer.

Sample Input 1

1 1 1

Sample Output 1

3

The three strings that satisfy the conditions are ACB, CBA, and BAC.

Sample Input 2

2 2 2

Sample Output 2

42

Sample Input 3

96 11 46

Sample Output 3

818015722

Sample Input 4

125132 102271 152064

Sample Output 4

128086069