30930번 - Ferris Wheel 다국어

문제

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.

입력

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 2ドルn$ 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.

제한

힌트

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

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