G - Wipeout 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 600 点

問題文

表に整数 1,2,\dots,N が書かれたカードが 1 枚ずつ、計 N 枚のカードが裏返しで一列に並べられています。
さらに、これらのカードの並び順は N! 通りの中から一様ランダムに定められます。
また、あなたは表に整数 1,2,\dots,N が書かれたカードが 1 枚ずつあること、カードが一様ランダムに並べられたことを知っていますが、カードの表に書かれている整数に関する情報はこれ以上持っていません。

あなたは以下のゲームを行います。

  • 最初、変数 x=1 とする。
  • x \le N である限り、以下の操作を繰り返す。 1 回の操作は以下の 3 つの手順からなる。
    • カードを 1 枚指定して、それを表に向ける。
    • カードに書かれた整数が x ならそのカードを食べ、 x に 1 加算する。
    • そうでないなら、そのカードを裏に向ける。あなたはそのカードに書かれた整数を永久に記憶しておくことができる。

あなたは常に全てのカードを食べ終わるまでの操作の総数の期待値が最小となるように行動します。
この場合、操作の総数が K 回となる確率はいくらでしょうか？ \text{mod }{998244353} で求めてください。

確率 \text{mod }{998244353} の定義

求める確率は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、求める有理数を既約分数 \frac{P}{Q} で表した時、Q {{}\not\equiv{}} 0 \pmod{998244353} となることが証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。

制約

  • 入力は全て整数
  • 1 \le N \le 5 \times 10^5
  • N \le K \le 10^9

入力

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

N K

出力

答えを出力せよ。

入力例 1

3 4

出力例 1

499122177

この入力について N=3 であり、各カードを並んでいる順に a,b,c と呼ぶことにします。
操作の総数の期待値が最小となるように行動するあなたの行動の一例を以下に示します。

  • まず、 a を表に向けます。
  • a に 1 が書かれていた場合、そのカードを食べます。
    • 次に、 b を表に向けます。
    • b に 2 が書かれていた場合、そのカードを食べます。
      • 次に c を表に向け、そこには必ず 3 が書かれているのでそれを食べます。この場合、操作 3 回で全てのカードを食べ終わり、このようになる確率は 1/6 です。
    • b に 3 が書かれていた場合、そのカードを裏に向けます。
      • 次に c を表に向け、そこには必ず 2 が書かれているのでそれを食べます。その後、 b を表に向け、食べます。この場合、操作 4 回で全てのカードを食べ終わり、このようになる確率は 1/6 です。
  • a に 2 が書かれていた場合、そのカードを裏に向けます。
    • 次に、 b を表に向けます。
    • b に 1 が書かれていた場合、そのカードを食べます。
      • 次に a を表に向け、食べます。次に c を表に向け、そこには必ず 3 が書かれているのでそれを食べます。この場合、操作 4 回で全てのカードを食べ終わり、このようになる確率は 1/6 です。
    • b に 3 が書かれていた場合、そのカードを裏に向けます。
      • この時点で、どのカードにどの整数が書かれているかが全てのカードについて判明しました。なので、 3 回操作を行い全てのカードを番号順に食べます。この場合、操作 5 回で全てのカードを食べ終わり、このようになる確率は 1/6 です。
  • a に 3 が書かれていた場合、そのカードを裏に向けます。
    • 次に、 b を表に向けます。
    • b に 1 が書かれていた場合、そのカードを食べます。
      • 次に c を表に向け、そこには必ず 2 が書かれているのでそれを食べます。その後、 a を表に向け、食べます。この場合、操作 4 回で全てのカードを食べ終わり、このようになる確率は 1/6 です。
    • b に 2 が書かれていた場合、そのカードを裏に向けます。
      • この時点で、どのカードにどの整数が書かれているかが全てのカードについて判明しました。なので、 3 回操作を行い全てのカードを番号順に食べます。この場合、操作 5 回で全てのカードを食べ終わり、このようになる確率は 1/6 です。

全てを統合すると、操作の総数が 3 回となる確率は 1/6 、 4 回となる確率は 1/2 、 5 回となる確率は 1/3 です。
本サンプルに対しては、 1/2 を \text{mod }{998244353} で表現した 499122177 を出力します。

入力例 2

3 6

出力例 2

0

入力例 3

500000 777777

出力例 3

251612105

Score : 600 points

Problem Statement

There are N cards arranged face down in a row, each with one of the integers 1,2,\dots,N written on its face.
The order of these cards is determined uniformly at random from the N! possible orders.
You know that there is exactly one card with each of the integers 1,2,\dots,N written on its face and that the cards were arranged uniformly at random, but you have no other information about the integers written on the faces of the cards.

You play the following game.

  • Initially, let the variable x=1.
  • As long as x \le N, repeat the following operation. One operation consists of the following three steps.
    • Specify one card and turn it face up.
    • If the integer written on the card is x, eat that card and add 1 to x.
    • Otherwise, turn that card face down. You can permanently remember the integer written on that card.

You always act so that the expected value of the total number of operations until all cards have been eaten is minimized.
In this case, what is the probability that the total number of operations is K? Find it modulo 998244353.

Definition of probability modulo 998244353

It can be proved that the sought probability is always a rational number. Also, under the constraints of this problem, it can be proved that when the rational number to be found is expressed as an irreducible fraction \frac{P}{Q}, we have Q {{}\not\equiv{}} 0 \pmod{998244353}. Therefore, there is a unique integer R satisfying R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353. Output this R.

Constraints

  • All input values are integers.
  • 1 \le N \le 5 \times 10^5
  • N \le K \le 10^9

Input

The input is given from Standard Input in the following format:

N K

Output

Output the answer.

Sample Input 1

3 4

Sample Output 1

499122177

For this input, N=3. Let us call the cards a,b,c in the order they are arranged.
Below is an example of your actions when acting so that the expected value of the total number of operations is minimized.

  • First, turn a face up.
  • If 1 is written on a, eat that card.
    • Next, turn b face up.
    • If 2 is written on b, eat that card.
      • Next, turn c face up; since 3 is necessarily written on it, eat it. In this case, you eat all cards in three operations, and the probability of this happening is 1/6.
    • If 3 is written on b, turn that card face down.
      • Next, turn c face up; since 2 is necessarily written on it, eat it. After that, turn b face up and eat it. In this case, you eat all cards in four operations, and the probability of this happening is 1/6.
  • If 2 is written on a, turn that card face down.
    • Next, turn b face up.
    • If 1 is written on b, eat that card.
      • Next, turn a face up and eat it. Next, turn c face up; since 3 is necessarily written on it, eat it. In this case, you eat all cards in four operations, and the probability of this happening is 1/6.
    • If 3 is written on b, turn that card face down.
      • At this point, it has become clear which integer is written on every one of the cards. So, perform three operations and eat all the cards in order of their numbers. In this case, you eat all cards in five operations, and the probability of this happening is 1/6.
  • If 3 is written on a, turn that card face down.
    • Next, turn b face up.
    • If 1 is written on b, eat that card.
      • Next, turn c face up; since 2 is necessarily written on it, eat it. After that, turn a face up and eat it. In this case, you eat all cards in four operations, and the probability of this happening is 1/6.
    • If 2 is written on b, turn that card face down.
      • At this point, it has become clear which integer is written on every one of the cards. So, perform three operations and eat all the cards in order of their numbers. In this case, you eat all cards in five operations, and the probability of this happening is 1/6.

Combining everything, the probability that the total number of operations is 3 is 1/6, the probability that it is 4 is 1/2, and the probability that it is 5 is 1/3.
For this sample, output 499122177, which represents 1/2 modulo 998244353.

Sample Input 2

3 6

Sample Output 2

0

Sample Input 3

500000 777777

Sample Output 3

251612105