大観覧車 Cosmo Clock 21 は横浜のランドマークで、街の夜景を美しく彩っています。ICPC 市も似たものを欲しがっています。
ICPC 市は、偶数個のゴンドラを持つイルミネーション付きの観覧車を建設する予定です。すべてのゴンドラを、与えられた候補色の集合のいずれか 1 色で塗ります。イルミネーションは次のように計画されています。
すべてのゴンドラを対にし、各ゴンドラはちょうど 1 つの対に属します。
同じ色の 2 つのゴンドラだけが対になれます。
対になったゴンドラを直線の LED ラインで結び、観覧車を照らします。
正面から見たとき、どの 2 本の LED ラインも交差しません。
ゴンドラの塗り方が適切であるとは、イルミネーション計画を満たす対の作り方が少なくとも 1 つ存在することです。
図 C.1. 適切な塗り方（左）と適切でない塗り方（右）の観覧車
ゴンドラ数と候補色数が与えられたとき、ゴンドラの適切な塗り方の数を求めてください。観覧車は回転するため、ある回転によって一致する 2 つの塗り方は同じとみなします。反対側から見たときにだけ一致する 2 つの塗り方は異なるとみなします。
入力
入力は次の形式の 1 つのテストケースからなります。
$$n\quad k$$
$n$ と $k$ は $1$ 以上 $3\times10^6$ 以下の整数です。ゴンドラ数と候補色数はそれぞれ $2n$ と $k$ です。
出力
ゴンドラの適切な塗り方の数を、素数 $998\,244\,353=2^{23}\times7\times17+1$ で割った余りを出力してください。
入出力例
入力 1
3 2
出力 1
6
入力 2
5 3
出力 2
372
入力 3
2023 1126
出力 3
900119621
注記
入力例 1 には、下の図に示す 6 つの適切な塗り方があります。
図 C.2. $n=3$、$k=2$ の場合の適切な塗り方