Ferris Wheel

Time limit6sMemory limit1024 MB

Summary

Count colorings of 2n gondolas on a circle with k colors that allow a non-crossing pairing of same-colored gondolas, modulo 998244353, up to rotation.

Level: Hard8 of 10
Topics: Combinatorics, Math, Number theory
Solved: No attempts yet

Problem

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.

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.

Input

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

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.

Hint

For the case $n = 3$ and $k = 2$ , there are six suitable colorings as listed in the figure below.

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

Examples3

Example 1
Input
```
3 2
```
Expected output
```
6
```
Example 2
Input
```
5 3
```
Expected output
```
372
```
Example 3
Input
```
2023 1126
```
Expected output
```
900119621
```