黑白石子

题目描述

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

从某个顶点开始，沿圆周每隔距离 $1$ 放置一枚黑色或白色的石子。这样一来，正 $N$ 边形的每条边上都有 $(D+1)$ 枚石子，总共放置了 $ND$ 枚石子。

求有多少种放置石子的方式，使得所有边上的白色石子数量都相同。答案对 $998244353$ 取模。

输入格式

输入按以下格式从标准输入给出：

$N$ $D$

输出格式

输出答案。

样例

3 2

10

共有 10 种方案。

299792458 3141

138897974

输出对 $998244353$ 取模后的值。

数据范围

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