Description

大型摩天轮 Cosmo Clock 21 是横滨的地标，为城市的夜景增添了美丽。ICPC 城市也想要类似的东西。

ICPC 城市计划建造一个带有偶数个座舱的发光摩天轮。所有座舱都将涂上给定候选颜色集中的一种颜色。照明计划如下：

• 所有座舱两两配对；每个座舱属于唯一的一对。
• 只有相同颜色的两个座舱可以配对。
• 配对的座舱之间用一条笔直的 LED 灯线连接以照亮摩天轮。
• 从前侧观察时，没有两条 LED 灯线相交。

如果一种座舱涂色方案允许至少一种满足照明计划的配对方式，则称其为 合适的。

:::align{center}

图 C.1. 具有合适（左）和 不 合适（右）涂色方案的摩天轮 :::

给定座舱数量和候选颜色数量，计算 合适的 座舱涂色方案的数量。由于摩天轮会旋转，如果两种涂色方案在某种旋转下重合，则认为它们是相同的。仅当从对侧观察时才重合的两种涂色方案被认为是不同的。

Input Format

输入由单个测试用例组成，格式如下。

$n$ 和 $k$ 是介于 $1$ 到 $3 \times 10^6$ 之间（含）的整数。座舱数量和候选颜色数量分别为 $2n$ 和 $k$。

Output Format

输出合适的座舱涂色方案数量，结果对 $998\,244\,353 = 2^{23} \times 7 \times 17 + 1$ 取模，这是一个质数。

3 2

6

5 3

372

2023 1126

900119621

Hint

对于样例输入 1，有六种合适的涂色方案，如下列图片所示。

:::align{center}

图 C.2. 当 $n=3$ 且 $k=2$ 时的合适涂色方案 :::