AT_abc256_g [ABC256G] Black and White Stones

题目描述

有一个边长为整数 $D$ 的正 $N$ 边形。

从一个顶点开始，每隔距离 $1$ 在周上放置一颗黑色或白色的石子。这样，每条边上会有 $D+1$ 颗石子，整个多边形上共放置 $ND$ 颗石子。

在所有石子的放法中，要求每条边上的白色石子的数量都相等。请问有多少种不同的放法？请输出答案对 $998244353$ 取模后的结果。

输入格式

输入以如下格式从标准输入读入。

$N$ $D$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 2

输出 #1

10

输入输出样例 #2

输入 #2

299792458 3141

输出 #2

138897974

说明/提示

限制条件

• $3 \leq N \leq 10^{12}$
• $1 \leq D \leq 10^4$
• 输入的所有值均为整数。

样例解释 1

如下图所示，共有 $10$ 种放法。

样例解释 2

请输出答案对 $998244353$ 取模后的结果。

由 ChatGPT 4.1 翻译