H - Random Swaps of Balls 解説 /

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

配点 : 450 点

問題文

N - 1 個の白いボールと 1 個の黒いボールがあります。これらの N 個のボールが横一列に並んでおり、はじめ黒いボールが最も左にあります。

高橋くんは、これから以下の操作をちょうど K 回行います。

  • 1 以上 N 以下の整数を一様ランダムに選ぶ試行を 2 回行う。選んだ整数をそれぞれ a, b とする。さらに、 a \neq b であれば左から a 番目のボールと b 番目のボールを交換する。

K 回の操作のあと黒いボールがある位置を左から x 番目とします。x の期待値を \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 < 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。

制約

  • 1 \leq N \leq 998244352
  • 1 \leq K \leq 10^5

入力

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

N K

出力

答えを 1 行に出力せよ。

入力例 1

2 1

出力例 1

499122178

1 回の操作が終わった後、黒いボールが左から 1 番目にある確率、 2 番目にある確率はそれぞれ \displaystyle \frac{1}{2} です。よって期待値は \displaystyle \frac{3}{2} です。

入力例 2

3 2

出力例 2

554580198

入力例 3

4 4

出力例 3

592707587

Score : 450 points

Problem Statement

There are N - 1 white balls and one black ball. These N balls are arranged in a row, with the black ball initially at the leftmost position.

Takahashi will perform the following operation exactly K times.

  • Choose an integer uniformly at random between 1 and N, inclusive, twice. Let a and b the chosen integers. If a \neq b, swap the a-th and b-th balls from the left.

After K operations, let the black ball be at the x-th position from the left. Find the expected value of x, modulo 998244353.

What is expected value modulo 998244353? It can be proved that the sought expected value will always be rational. Additionally, under the constraints of this problem, it can be proved that if this value is expressed as an irreducible fraction \frac{P}{Q}, then Q \not \equiv 0 \pmod{998244353}. Therefore, there exists a unique integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Report this R.

Constraints

  • 1 \leq N \leq 998244352
  • 1 \leq K \leq 10^5

Input

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

N K

Output

Print the answer in one line.

Sample Input 1

2 1

Sample Output 1

499122178

After one operation, the probabilities that the black ball is at the 1st position and the 2nd position from the left are both \displaystyle \frac{1}{2}. Thus, the expected value is \displaystyle \frac{3}{2}.

Sample Input 2

3 2

Sample Output 2

554580198

Sample Input 3

4 4

Sample Output 3

592707587