分数: 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).)
找出以正方形结尾的路线数 (X, Y, Z) 正好之后 N 传送。
换句话说,找到的序列数 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) 正好之后 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
1 0 0 0
示例输出 2
0
请注意,确切地说 N 应该进行传送,并且不允许他停留在同一位置。
示例输入 3
314 15 92 65
示例输出 3
106580952
请务必打印数字模数 998244353.