Contest Duration: - (local time) (100 minutes) Back to Home
G - Black and White Stones /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

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

### 入力

N D


### 入力例 1

3 2


### 出力例 1

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


### 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.