题目描述

高橋君は無限に広がる三次元グリッドのマス $(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$ で割った余りを出力してください。

输入格式

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

$N$ $X$ $Y$ $Z$

输出格式

答えを $998244353$ で割った余りを出力せよ。

题目大意

在一个空间直角坐标系中移动，每步可以沿着坐标轴正/负方向移动一个单位的长度。

给定 $N,X,Y,Z$ ，求：

恰好 $N$ 步，从点 $(0,0,0)$ 走到点 $(X,Y,Z)$ 的方案数。

答案对 $998244353$ 取模。

3 2 0 -1

3

1 0 0 0

0

314 15 92 65

106580952

提示

制約

• $1\ \leq\ N\ \leq\ 10^7$
• $-10^7\ \leq\ X,\ Y,\ Z\ \leq\ 10^7$
• $N,\ X,\ Y,\ Z$ は整数

Sample Explanation 1

ちょうど $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) $

Sample Explanation 2

ちょうど $N$ 回の瞬間移動を行わなければならないことと、瞬間移動の際には移動せずにその場にとどまることは出来ないことに注意してください。

Sample Explanation 3

答えを $998244353$ で割った余りを出力することに注意してください。