题目描述

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

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

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

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

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

输入格式

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

$N$ $W$

输出格式

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

题目大意

给定一排 $n$ 枚硬币，初始时所有硬币正面向上。

Snuke 会等概率地选择一个长度为 $n$ 的排列 $p = (p_1, p_2, \dots, p_n)$，并执行 $n$ 次操作。第 $i$ 次操作会执行如下步骤：

• 若第 $i$ 枚硬币是反面朝上的，什么也不做。
• 若第 $i$ 枚硬币是正面朝上的，翻转它，并翻转第 $p_i$ 枚硬币。

给定 $w$。设 $n$ 次操作完后正面朝上的硬币数为 $k$，则这排列的贡献即为 $w^k$。

你需要求出这贡献的期望值乘 $n!$ 后在模 $998244353$ 意义下的值。容易证明这值定是整数。

$1\le n\le 2\times 10^5, \ 1\le w < 998244353$。

4 2

90

2 100

10001

200000 12345

541410753

提示

制約

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

Sample Explanation 1

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

Sample Explanation 3

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