D - Yet Another ABC String

Contest Duration: 2022-08-14(Sun) 12:10 - 2022-08-14(Sun) 15:10 (local time) (180 minutes) Back to Home

D - Yet Another ABC String Editorial

Time Limit: 2 sec / Memory Limit: 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$

出力

答えを出力せよ．

入力例 1Copy

Copy

1 1 1

出力例 1Copy

Copy

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

入力例 2Copy

Copy

2 2 2

出力例 2Copy

Copy

入力例 3Copy

Copy

96 11 46

出力例 3Copy

Copy

818015722

入力例 4Copy

Copy

125132 102271 152064

出力例 4Copy

Copy

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 1Copy

Copy

1 1 1

Sample Output 1Copy

Copy

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

Sample Input 2Copy

Copy

2 2 2

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

96 11 46

Sample Output 3Copy

Copy

818015722

Sample Input 4Copy

Copy

125132 102271 152064

Sample Output 4Copy

Copy

128086069