E - Count 123

コンテスト時間: 2026-05-16 21:00:00+0900 ~ 2026-05-16 22:40:00+0900 (100分) AtCoderホームへ戻る

E - Count 123 解説

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

配点 : 450 点

問題文

以下の条件をすべて満たす長さ X_1+X_2+X_3 の数列 A = (a_1, \cdots, a_{X_1 + X_2 + X_3}) としてあり得るものの個数を 998244353 で割ったあまりを求めてください。

A は 1 を X_1 個、2 を X_2 個、3 を X_3 個含む。
隣接する要素の差の絶対値は 1 以下である。つまり、1 \leq i \leq X_1+X_2+X_3-1 を満たす任意の整数 i について、|a_{i+1} - a_i| \leq 1 が成り立つ。

制約

1 \leq X_1, X_2, X_3 \leq 10^6
入力される値はすべて整数

入力

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

X_1 X_2 X_3

出力

答えを出力せよ。

入力例 1

2 2 1

出力例 1

条件を満たす数列は以下の 9 通りです。

(1, 1, 2, 2, 3)
(1, 1, 2, 3, 2)
(1, 2, 1, 2, 3)
(1, 2, 3, 2, 1)
(2, 1, 1, 2, 3)
(2, 3, 2, 1, 1)
(3, 2, 1, 1, 2)
(3, 2, 1, 2, 1)
(3, 2, 2, 1, 1)

入力例 2

5 3 4

出力例 2

入力例 3

998244 998353 998107

出力例 3

701926019

Score : 450 points

Problem Statement

Find the number, modulo 998244353, of sequences A = (a_1, \cdots, a_{X_1 + X_2 + X_3}) of length X_1+X_2+X_3 that satisfy all of the following conditions.

A contains exactly X_1 copies of 1, exactly X_2 copies of 2, and exactly X_3 copies of 3.
The absolute difference between adjacent elements is at most 1. That is, for every integer i satisfying 1 \leq i \leq X_1+X_2+X_3-1, we have |a_{i+1} - a_i| \leq 1.

Constraints

1 \leq X_1, X_2, X_3 \leq 10^6
All input values are integers.

Input

The input is given from Standard Input in the following format:

X_1 X_2 X_3

Output

Output the answer.

Sample Input 1

2 2 1

Sample Output 1

The sequences satisfying the conditions are the following nine:

(1, 1, 2, 2, 3)
(1, 1, 2, 3, 2)
(1, 2, 1, 2, 3)
(1, 2, 3, 2, 1)
(2, 1, 1, 2, 3)
(2, 3, 2, 1, 1)
(3, 2, 1, 1, 2)
(3, 2, 1, 2, 1)
(3, 2, 2, 1, 1)

Sample Input 2

5 3 4

Sample Output 2

Sample Input 3

998244 998353 998107

Sample Output 3

701926019