← 返回题目列表

AtCoder · abc240_g

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

找出以正方形结尾的路线数 (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.