配点 : $1000$ 点

問題文

$1,2,\ldots,N$ の番号がついた $N$ 枚のコインが並べられています。 はじめ、全てのコインは表を向いています。

すぬけ君は $(1,\ldots,N)$ を並び替えて得られる順列 $p$ を等確率で $1$ つ選び $N$ 回操作を行います。 $i$ 回目の操作では以下の処理が行われます。

• $i$ 番のコインが裏向きならば何もしない。
• $i$ 番のコインが表向きならば $i$ 番のコインをひっくり返した後 $p_i$ 番のコインをひっくり返す。

$N$ 回の操作の後、表向きのコインの枚数を $k$ としてすぬけ君はお母さんから $W^k$ 円もらえます。

すぬけ君が得られるお金の期待値に $N!$ をかけた値(これは整数になることが証明できます)を $998244353$ で割ったあまりを求めてください。

制約

• 与えられる入力は全て整数
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq W < 998244353$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $W$

出力

すぬけ君が得られるお金の期待値に $N!$ をかけた値を $998244353$ で割った余りを出力せよ。

4 2

90

• $p=(1,4,2,3)$ のとき、以下のように操作が行われます。- $1$ 回目の操作では $1$ 番のコインが裏向きになり、その後 $1$ 番のコインが表向きになります。
  • $2$ 回目の操作では $2$ 番のコインが裏向きになり、その後 $4$ 番のコインが裏向きになります。
  • $3$ 回目の操作では $3$ 番のコインが裏向きになり、その後 $2$ 番のコインが表向きになります。
  • $4$ 回目の操作では何も行われません。
• $1$ 回目の操作では $1$ 番のコインが裏向きになり、その後 $1$ 番のコインが表向きになります。
• $2$ 回目の操作では $2$ 番のコインが裏向きになり、その後 $4$ 番のコインが裏向きになります。
• $3$ 回目の操作では $3$ 番のコインが裏向きになり、その後 $2$ 番のコインが表向きになります。
• $4$ 回目の操作では何も行われません。
• 最終的に $2$ 枚のコインが表向きのため、$4$ 円もらえます。

2 100

10001

200000 12345

541410753

• $998244353$ で割ったあまりを求めるのを忘れずに。