分数: 900 点
问题陈述
我们有一系列 N 整数: x=(x_0,x_1,\cdots,x_{N-1})。 最初, x_i=0 对于每个 i (0 \leq i \leq N-1).
Snuke 将执行以下操作 正是 M 次:
- 选择两个不同的索引 i, j (0 \leq i,j \leq N-1,\ i \neq j)。 然后,更换 x_i 与 x_i+2 和 x_j 与 x_j+1.
找出之后可能产生的不同序列的数量 M 操作。 由于它可能很大,请计算计数模 998244353.
约束
- 2 \leq N \leq 10^6
- 1 \leq M \leq 5 \times 10^5
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M
输出
打印之后可能产生的不同序列的数量 M 运算,模数 998244353.
示例输入 1
2 2
示例输出 1
3
两次操作后,可能出现三种结果: 经过以下操作序列后可能会产生
- x=(2,4)
- x=(3,3)
- x=(4,2)
例如, x=(3,3) :
- 首先,选择 i=0,j=1,改变 x 来自 (0,0) to (2,1).
- 二、选择 i=1,j=0,改变 x 来自 (2,1) to (3,3).
示例输入 2
3 2
示例输出 2
19
示例输入 3
10 10
示例输出 3
211428932
示例输入 4
100000 50000
示例输出 4
3463133