配点 : $600$ 点

問題文

一辺の長さが整数 $D$ の正 $N$ 角形があります。

頂点から始めて、周上に距離 $1$ ごとに黒い石か白い石を置きます。これにより、$N$ 角形の各辺上に $D+1$ 個、全体で $ND$ 個の石が置かれます。

石の置き方のうち、各辺上にある白い石の個数が等しくなるようなものは何通りありますか？　$998244353$ で割った余りを求めてください。

制約

• $3 \leq N \leq 10^{12}$
• $1 \leq D \leq 10^4$
• 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$ $D$

出力

答えを出力せよ。

3 2

10

下図の $10$ 通りがあります。

299792458 3141

138897974

$998244353$ で割った余りを求めてください。