G - 黑白石头

得分: $600$ 分

问题描述

有一正 $N$ 边形，边长为 $D$。

从一个顶点开始，我们按照间隔 $1$ 在边上放置黑色或白色的石头。结果是，$N$ 边形的每条边上都有 $(D+1)$ 个石头，总共有 $ND$ 个石头。

有多少种放置石头的方式，使得所有边上的白色石头数量相同？给出结果对 $998244353$ 取模后的值。

约束

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

输入

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

$N$ $D$

输出

输出结果。

3 2

10

有 $10$ 种方式，如下所示:

299792458 3141

138897974

给出结果对 $998244353$ 取模。