102566: [AtCoder]ABC256 G - Black and White Stones

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

问题描述

有一个边长为$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$。