/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
長さ N の数列 x=(x_0,x_1,\cdots,x_{N-1}) があります。 最初、すべての i (0 \leq i \leq N-1) について x_i=0 です。
すぬけさんは、次の操作をちょうど M 回行います。
- 相異なる添字 i,j (0 \leq i,j \leq N-1,\ i \neq j) を選ぶ。 そして、x_i を x_i+2 で置き換える。また、x_j を x_j+1 で置き換える。
最終的な数列 x の状態としてありうるものが何通りあるかを求めてください。 ただし、答えは非常に大きくなることがあるので、998244353 で割ったあまりを求めてください。
制約
- 2 \leq N \leq 10^6
- 1 \leq M \leq 5 \times 10^5
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
最終的な数列 x の状態としてありうるものが何通りあるかを 998244353 で割ったあまりを出力せよ。
入力例 1
2 2
出力例 1
3
2 回の操作後の x の状態としてありうるものは以下の 3 通りです。
- x=(2,4)
- x=(3,3)
- x=(4,2)
たとえば、x=(3,3) としたい場合、次のように操作すればよいです。
- 1 回目の操作：i=0,j=1 とする。x は (0,0) から (2,1) へ変化する。
- 2 回目の操作：i=1,j=0 とする。x は (2,1) から (3,3) へ変化する。
入力例 2
3 2
出力例 2
19
入力例 3
10 10
出力例 3
211428932
入力例 4
100000 50000
出力例 4
3463133
Score : 900 points
Problem Statement
We have a sequence of N integers: x=(x_0,x_1,\cdots,x_{N-1}). Initially, x_i=0 for each i (0 \leq i \leq N-1).
Snuke will perform the following operation exactly M times:
- Choose two distinct indices i, j (0 \leq i,j \leq N-1,\ i \neq j). Then, replace x_i with x_i+2 and x_j with x_j+1.
Find the number of different sequences that can result after M operations. Since it can be enormous, compute the count modulo 998244353.
Constraints
- 2 \leq N \leq 10^6
- 1 \leq M \leq 5 \times 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
Output
Print the number of different sequences that can result after M operations, modulo 998244353.
Sample Input 1
2 2
Sample Output 1
3
After two operations, there are three possible outcomes:
- x=(2,4)
- x=(3,3)
- x=(4,2)
For example, x=(3,3) can result after the following sequence of operations:
- First, choose i=0,j=1, changing x from (0,0) to (2,1).
- Second, choose i=1,j=0, changing x from (2,1) to (3,3).
Sample Input 2
3 2
Sample Output 2
19
Sample Input 3
10 10
Sample Output 3
211428932
Sample Input 4
100000 50000
Sample Output 4
3463133