/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
高橋君は無限に広がる三次元グリッドのマス (0, 0, 0) にいます。
高橋君は瞬間移動によってマスからマスへ移動する能力を持っています。 マス (x, y, z) にいるとき、瞬間移動を 1 回行うと (x+1, y, z), (x-1, y, z), (x, y+1, z), (x, y-1, z), (x, y, z+1), (x, y, z-1) のいずれかのマスに移動します。（マス (x, y, z) にとどまることは出来ないことに注意してください。）
ちょうど N 回の瞬間移動を行った後にマス (X, Y, Z) にいるような高橋君の移動経路が何通りあるかを求めてください。
すなわち、整数の 3 つ組を N+1 個並べた列 \big( (x_0, y_0, z_0), (x_1, y_1, z_1), (x_2, y_2, z_2), \ldots, (x_N, y_N, z_N)\big) であって、下記の 3 つの条件をすべて満たすものの個数を求めてください。
- (x_0, y_0, z_0) = (0, 0, 0)
- (x_N, y_N, z_N) = (X, Y, Z)
- i = 1, 2, \ldots, N について、|x_i-x_{i-1}| + |y_i-y_{i-1}| + |z_i-z_{i-1}| = 1
ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割った余りを出力してください。
制約
- 1 \leq N \leq 10^7
- -10^7 \leq X, Y, Z \leq 10^7
- N, X, Y, Z は整数
入力
入力は以下の形式で標準入力から与えられる。
N X Y Z
出力
答えを 998244353 で割った余りを出力せよ。
入力例 1
3 2 0 -1
出力例 1
3
ちょうど 3 回の瞬間移動を行った後にマス (2, 0, -1) にいるような高橋君の移動経路は、下記の 3 通り存在します。
- (0, 0, 0) \rightarrow (1, 0, 0) \rightarrow (2, 0, 0) \rightarrow(2, 0, -1)
- (0, 0, 0) \rightarrow (1, 0, 0) \rightarrow (1, 0, -1) \rightarrow(2, 0, -1)
- (0, 0, 0) \rightarrow (0, 0, -1) \rightarrow (1, 0, -1) \rightarrow(2, 0, -1)
入力例 2
1 0 0 0
出力例 2
0
ちょうど N 回の瞬間移動を行わなければならないことと、瞬間移動の際には移動せずにその場にとどまることは出来ないことに注意してください。
入力例 3
314 15 92 65
出力例 3
106580952
答えを 998244353 で割った余りを出力することに注意してください。
Score : 600 points
Problem Statement
Takahashi is in the square (0, 0, 0) in an infinite three-dimensional grid.
He can teleport between squares. From the square (x, y, z), he can move to (x+1, y, z), (x-1, y, z), (x, y+1, z), (x, y-1, z), (x, y, z+1), or (x, y, z-1) in one teleport. (Note that he cannot stay in the square (x, y, z).)
Find the number of routes ending in the square (X, Y, Z) after exactly N teleports.
In other words, find the number of sequences of N+1 triples of integers \big( (x_0, y_0, z_0), (x_1, y_1, z_1), (x_2, y_2, z_2), \ldots, (x_N, y_N, z_N)\big) that satisfy all three conditions below.
- (x_0, y_0, z_0) = (0, 0, 0).
- (x_N, y_N, z_N) = (X, Y, Z).
- |x_i-x_{i-1}| + |y_i-y_{i-1}| + |z_i-z_{i-1}| = 1 for each i = 1, 2, \ldots, N.
Since the number can be enormous, print it modulo 998244353.
Constraints
- 1 \leq N \leq 10^7
- -10^7 \leq X, Y, Z \leq 10^7
- N, X, Y, and Z are integers.
Input
Input is given from Standard Input in the following format:
N X Y Z
Output
Print the number modulo 998244353.
Sample Input 1
3 2 0 -1
Sample Output 1
3
There are three routes ending in the square (2, 0, -1) after exactly 3 teleports:
- (0, 0, 0) \rightarrow (1, 0, 0) \rightarrow (2, 0, 0) \rightarrow(2, 0, -1)
- (0, 0, 0) \rightarrow (1, 0, 0) \rightarrow (1, 0, -1) \rightarrow(2, 0, -1)
- (0, 0, 0) \rightarrow (0, 0, -1) \rightarrow (1, 0, -1) \rightarrow(2, 0, -1)
Sample Input 2
1 0 0 0
Sample Output 2
0
Note that exactly N teleports should be performed, and they do not allow him to stay in the same position.
Sample Input 3
314 15 92 65
Sample Output 3
106580952
Be sure to print the number modulo 998244353.