102406: [AtCoder]ABC240 G - Teleporting Takahashi

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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$.

Input

题意翻译

在一个空间直角坐标系中移动,每步可以沿着坐标轴正/负方向移动一个单位的长度。 给定 $N,X,Y,Z$ ,求: 恰好 $N$ 步,从点 $(0,0,0)$ 走到点 $(X,Y,Z)$ 的方案数。 答案对 $998244353$ 取模。

Output

得分:600分

问题描述

高桥在无限三维网格中的原点$(0, 0, 0)$。

他可以瞬间移动到其他格子之间。 从格子$(x, y, z)$,他可以移动到$(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)$的路线数量。

换句话说,找出满足以下三个条件的$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)$。

  • $(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$对于每个$i = 1, 2, \ldots, N$。

由于数字可能非常大,请取模$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)$:

  • $(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$输出数字。

加入题单

上一题 下一题 算法标签: