E - Fruit Lineup Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

A 個のリンゴと B 個のオレンジと C 個のバナナと D 個のブドウがあります。
これらの A+B+C+D 個の果物を、以下の条件全てを満たすように左右一列に並べる方法は何通りありますか？答えを 998244353 で割った余りを求めてください。

  • リンゴはすべて、バナナよりも左側に並べる。
  • リンゴはすべて、ブドウよりも左側に並べる。
  • オレンジはすべて、ブドウよりも左側に並べる。

ただし、同じ種類の果物同士は区別できないとします。

制約

  • 1 \leq A \leq 10^6
  • 1 \leq B \leq 10^6
  • 1 \leq C \leq 10^6
  • 1 \leq D \leq 10^6
  • A, B, C, D は全て整数

入力

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

A B C D

出力

果物を問題文の条件を満たすように左右一列に並べる方法の個数を 998244353 で割った余りを出力せよ。

入力例 1

1 1 1 1

出力例 1

5

問題文の条件を満たす果物の並べ方は次の 5 通りです。

  • リンゴ, オレンジ, バナナ, ブドウ
  • リンゴ, オレンジ, ブドウ, バナナ
  • リンゴ, バナナ, オレンジ, ブドウ
  • オレンジ, リンゴ, バナナ, ブドウ
  • オレンジ, リンゴ, ブドウ, バナナ

入力例 2

1 2 4 8

出力例 2

2211

入力例 3

834150 21994 467364 994225

出力例 3

947921688

Score : 475 points

Problem Statement

You have A apples, B oranges, C bananas, and D grapes.
How many ways are there to arrange these A+B+C+D fruits in a single row from left to right so that all of the following conditions hold? Find the count modulo 998244353.

  • Every apple is placed to the left of every banana.
  • Every apple is placed to the left of every grape.
  • Every orange is placed to the left of every grape.

Here, the apples are indistinguishable; the same goes for the oranges, the bananas, and the grapes.

Constraints

  • 1 \le A \le 10^6
  • 1 \le B \le 10^6
  • 1 \le C \le 10^6
  • 1 \le D \le 10^6
  • A, B, C, and D are integers.

Input

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

A B C D

Output

Output the number, modulo 998244353, of valid arrangements.

Sample Input 1

1 1 1 1

Sample Output 1

5

There are five valid arrangements:

  • apple, orange, banana, grape
  • apple, orange, grape, banana
  • apple, banana, orange, grape
  • orange, apple, banana, grape
  • orange, apple, grape, banana

Sample Input 2

1 2 4 8

Sample Output 2

2211

Sample Input 3

834150 21994 467364 994225

Sample Output 3

947921688