

Time Limit: 2 sec / Memory Limit: 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:
Sample Input 2
299792458 3141
Sample Output 2
138897974
Find the count modulo 998244353.