P14816 [ICPC 2023 Yokohama R] Ferris Wheel

大型摩天轮 Cosmo Clock 21 是横滨的地标，为城市的夜景增添了美丽。ICPC 城市也想要类似的东西。 ICPC 城市计划建造一个带有偶数个座舱的发光摩天轮。所有座舱都将涂上给定候选颜色集中的一种颜色。照明计划如下： - 所有座舱两两配对；每个座舱属于唯一的一对。 - 只有相同颜色的两个座舱可以配对。 - 配对的座舱之间用一条笔直的 LED 灯线连接以照亮摩天轮。 - 从前侧观察时，没有两条 LED 灯线相交。 如果一种座舱涂色方案允许至少一种满足照明计划的配对方式，则称其为 **合适的**。 :::align{center}  图 C.1. 具有合适（左）和 **不** 合适（右）涂色方案的摩天轮 ::: 给定座舱数量和候选颜色数量，计算 **合适的** 座舱涂色方案的数量。由于摩天轮会旋转，如果两种涂色方案在某种旋转下重合，则认为它们是相同的。仅当从对侧观察时才重合的两种涂色方案被认为是不同的。

输入由单个测试用例组成，格式如下。 $$ n\ k $$ $n$ 和 $k$ 是介于 $1$ 到 $3 \times 10^6$ 之间（含）的整数。座舱数量和候选颜色数量分别为 $2n$ 和 $k$。

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

对于样例输入 1，有六种合适的涂色方案，如下列图片所示。 :::align{center}  图 C.2. 当 $n=3$ 且 $k=2$ 时的合适涂色方案 :::