题目描述

有一个边长为 $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$ 种方法，如下所示：

示例输入2

299792458 3141

示例输出2

138897974

将计数取模 $998244353$。