传送高桥

题目描述

高桥位于无限三维网格中的格子 $(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$ 取模后输出。

输入格式

输入按以下格式从标准输入给出:

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$ 取模后的结果。

数据范围

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