当前没有测试数据。

G - 传送门的使用

得分：$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$ 个三元组 $(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)$ 的数量：

• $(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$ 取模。

约束条件

• $1 \leq N \leq 10^7$
• $-10^7 \leq X, Y, Z \leq 10^7$
• $N$，$X$，$Y$ 和 $Z$ 是整数。

输入

输入从标准输入中获得，格式如下：

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

输出

输出结果对 $998244353$ 取模。

3 2 0 -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)$

1 0 0 0

0

注意需要恰好进行 $N$ 次传送，且不允许停留在同一位置。

314 15 92 65

106580952

请务必将结果对 $998244353$ 取模。