AT_abc240_g [ABC240G] Teleporting 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)$。请注意，他不能停留在原地。

请你计算，恰好经过 $N$ 次瞬间移动后，高桥君位于格点 $(X, Y, Z)$ 的移动路径有多少种。

也就是说，求满足以下三个条件的整数三元组序列 $\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$ 取模的结果。

输入格式

输入为一行，包含四个整数：

$N\ X\ Y\ Z$

输出格式

输出一个整数，表示答案对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

3 2 0 -1

输出 #1

3

输入输出样例 #2

输入 #2

1 0 0 0

输出 #2

0

输入输出样例 #3

输入 #3

314 15 92 65

输出 #3

106580952

说明/提示

数据范围

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

样例解释 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)$

样例解释 2

请注意，必须恰好进行 $N$ 次瞬间移动，并且每次瞬间移动时不能停留在原地。

样例解释 3

请注意，输出的答案需要对 $998244353$ 取模。

由 ChatGPT 4.1 翻译