/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1800 点
問題文
以下の無向グラフにおいて、S から S へのウォークであって辺 ST, TU, UV, VS をそれぞれ a, b, c, d 回通るもの (向きは不問) の数を 998,244,353 で割った余りを求めてください。
注記
S から S へのウォークとは、頂点の列 v_0 = S, v_1, \ldots, v_k = S であって、各 i (0 \leq i < k) について v_i と v_{i+1} を結ぶ辺があるものをいいます。 2 つのウォークは、列として異なるときに異なるとみなされます。
制約
- 1 \leq a, b, c, d \leq 500,000
- 入力中の全ての値は整数である。
入力
入力は標準入力から以下の形式で与えられる。
a b c d
出力
答えを出力せよ。
入力例 1
2 2 2 2
出力例 1
10
条件を満たすウォークは 10 個あり、その一例は S \rightarrow T \rightarrow U \rightarrow V \rightarrow U \rightarrow T \rightarrow S \rightarrow V \rightarrow S です。
入力例 2
1 2 3 4
出力例 2
0
入力例 3
470000 480000 490000 500000
出力例 3
712808431
Score : 1800 points
Problem Statement
In the following undirected graph, count the number of walks from S to S that pass through the edges ST, TU, UV, VS (in any direction) exactly a, b, c, d times, respectively, modulo 998,244,353.
Notes
A walk from S to S is a sequence of vertices v_0 = S, v_1, \ldots, v_k = S such that for each i (0 \leq i < k), there is an edge between v_i and v_{i+1}. Two walks are considered distinct if they are distinct as sequences.
Constraints
- 1 \leq a, b, c, d \leq 500,000
- All values in the input are integers.
Input
Input is given from Standard Input in the following format:
a b c d
Output
Print the answer.
Sample Input 1
2 2 2 2
Sample Output 1
10
There are 10 walks that satisfy the condition. One example of such a walk is S \rightarrow T \rightarrow U \rightarrow V \rightarrow U \rightarrow T \rightarrow S \rightarrow V \rightarrow S.
Sample Input 2
1 2 3 4
Sample Output 2
0
Sample Input 3
470000 480000 490000 500000
Sample Output 3
712808431