#abc256g. [abc256_g]Black and White Stones

[abc256_g]Black and White Stones

問題文

一辺の長さが整数 DD の正 NN 角形があります。

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

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

制約

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

入力

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

NN DD

出力

答えを出力せよ。


入力例 1

3 2

出力例 1

10

下図の 1010 通りがあります。

図


入力例 2

299792458 3141

出力例 2

138897974

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