F - Flipping Coins Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 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 で割った余りを出力せよ。

入力例 1

4 2

出力例 1

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

入力例 2

2 100

出力例 2

10001

入力例 3

200000 12345

出力例 3

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

Score : 1000 points

Problem Statement

There are N coins numbered 1, 2, \ldots, N arranged in a row. Initially, all coins face up.

Snuke chooses a permutation p of (1,\ldots,N) with equal probability, and do N operations. The i-th operation does the following.

  • If the coin numbered i faces down, do nothing.
  • If the coin numbered i faces up, turn that coin over and then turn over the coin numbered p_i.

After the N operations, Snuke will receive W^k yen (Japanese currency) from his mother, where k is the number of coins facing up.

Find the expected value of the amount Snuke will get, multiplied by N! (it can be proved that this is an integer), modulo 998244353.

Constraints

  • All values in input are integers.
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq W < 998244353

Input

Input is given from Standard Input in the following format:

N W

Output

Print the expected value of the amount Snuke will get, multiplied by N!, modulo 998244353.

Sample Input 1

4 2

Sample Output 1

90
  • When p=(1,4,2,3), the operations go as follows.
    • In the 1-st operation, the coin numbered 1 faces down, and then the coin numbered 1 faces up.
    • In the 2-nd operation, the coin numbered 2 faces down, and then the coin numbered 4 faces down.
    • In the 3-rd operation, the coin numbered 3 faces down, and then the coin numbered 2 faces up.
    • In the 4-th operation, nothing is done.
  • In the end, two coins face up, so he receives 4 yen.

Sample Input 2

2 100

Sample Output 2

10001

Sample Input 3

200000 12345

Sample Output 3

541410753
  • Be sure to find the value modulo 998244353.