Black and White Stones

题目描述

有一个边长为 $D$ 的正 $N$ 边形。 从某个顶点起，我们沿周长以间隔 $1$ 放置黑色或白色的棋子。因此，正 $N$ 边形的每条边上将有 $(D+1)$ 个棋子，总共有 $ND$ 个棋子。 有多少种放置棋子的方法使得所有边上白棋的数量都相同？请计算结果对 $998244353$ 取模的值。

输入格式

输入按标准输入给出，格式如下： $N$ $D$

输出格式

输出答案。

3 2

10

299792458 3141

138897974

提示

$3 \leq N \leq 10^{12}$ $1 \leq D \leq 10^4$ 输入中的所有值均为整数。有 $10$ 种方法，如下所示：
对 $998244353$ 取模后计数。

标签: AtCoder|abc256G

来源

AtCoder|abc256G