题目描述

The big Ferris wheel, Cosmo Clock 21, is a landmark of Yokohama and adds beauty to the city’s night view. The ICPC city also wants something similar.

The ICPC city plans to build an illuminated Ferris wheel with an even number of gondolas. All the gondolas are to be colored with one of the given set of candidate colors. The illumination is planned as follows.

• All the gondolas are paired up; every gondola belongs to a single pair.
• Only two gondolas of the same color can form a pair.
• Paired gondolas are connected with a straight LED line to illuminate the wheel.
• No two LED lines cross when looked from the front side.

A coloring of gondolas is suitable if it allows at least one way of pairing for the illumination plan.

:::align{center}

Figure C.1. Ferris wheels with suitable (left) and not suitable (right) colorings :::

Given the numbers of gondolas and candidate colors, count the number of suitable colorings of gondolas. Since the Ferris wheel rotates, two colorings are considered the same if they coincide under a certain rotation. Two colorings that coincide only when looked from the opposite sides are considered different.

输入格式

The input consists of a single test case in the following format.

$$n\ k$$

$n$ and $k$ are integers between 1 and $3 \times 10^6$, inclusive. The numbers of gondolas and candidate colors are $2n$ and $k$, respectively.

输出格式

Output the number of suitable colorings of gondolas in modulo $998\,244\,353 = 2^{23} \times 7 \times 17 + 1$, which is a prime number.

3 2

6

5 3

372

2023 1126

900119621

提示

For Sample Input 1, there are six suitable colorings as listed in the figure below.

:::align{center}

Figure C.2. Suitable colorings in case of $n=3$ and $k=2$ :::