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

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

你现在有一个正 $n$ 边形 , 边长为 $d$。从顶点开始,你每个长度 $1$ 放一个石子,白色或者黑色。换句话说,每条边上有 $d+1$ 个石子,相邻两边公用一个石子。 请问有多少种方案,使得所有边上的白色石子数量相同。对 $998244353$ 取模。 $n \le 10^{12}$,$d\le 10^4$。注意 $n$ 的范围。

Output

得分:$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$种方法,如下所示:

Figure


样例输入2

299792458 3141

样例输出2

138897974

取答案模$998244353$。

加入题单

上一题 下一题 算法标签: