Score : $600$ points

问题描述

存在一个边长为 $D$ 的正 $N$ 边形。

从一个顶点出发，我们在圆周上每隔 $1$ 个单位放置黑色或白色的石子。因此，每个 $N$ 边形的边将会有 $(D+1)$ 个石子，总共放置 $ND$ 个石子。

有多少种方法可以放置石子，使得所有边上的白色石子数量相同？请在模 $998244353$ 的意义下求出方案数。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 10:54:20