C - GP 2

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_ix_i+2 で置き換える。また、x_jx_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