AT_abc240_g [ABC240G] Teleporting Takahashi

[problemUrl]: https://atcoder.jp/contests/abc240/tasks/abc240_g 高橋君は無限に広がる三次元グリッドのマス $ (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 $ で割った余りを出力せよ。

### 制約 - $ 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 $ で割った余りを出力することに注意してください。