Score : $600$ points

问题描述

Takahashi在无限三维网格中的点 $(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)$。
• 对于每个 $i = 1, 2, \ldots, N$，满足 $|x_i-x_{i-1}| + |y_i-y_{i-1}| + |z_i-z_{i-1}| = 1$。

由于这个数字可能非常大，请输出模 $998244353$ 后的结果。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 10:22:15