配点 : $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$ で割ったあまりを出力せよ。

2 2

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)$ へ変化する。

3 2

19

10 10

211428932

100000 50000

3463133