G - Black and White Stones 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

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

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

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

制約

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

入力

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

N D

出力

答えを出力せよ。

入力例 1

3 2

出力例 1

10

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

図

入力例 2

299792458 3141

出力例 2

138897974

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

Score : 600 points

Problem Statement

There is a regular N-gon with side length D.

Starting from a vertex, we place black or white stones on the circumference at intervals of 1. As a result, each edge of the N-gon will have (D+1) stones on it, for a total of ND stones.

How many ways are there to place stones so that all edges have the same number of white stones on them? Find the count modulo 998244353.

Constraints

  • 3 \leq N \leq 10^{12}
  • 1 \leq D \leq 10^4
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N D

Output

Print the answer.

Sample Input 1

3 2

Sample Output 1

10

There are 10 ways, as follows:

Figure

Sample Input 2

299792458 3141

Sample Output 2

138897974

Find the count modulo 998244353.