← 返回题目列表

AtCoder · abc360_e

H. 球的随机交换

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

有 N - 1 白球和一个黑球。这些 N 球排列成一排,黑球最初位于最左边的位置。

Takahashi 将准确执行以下操作 K 次。

  • 均匀地随机选择一个整数 1 和 N,包含在内,两次。让 a 和 b 所选整数。如果 a \neq b,交换 a-th 和 b从左边数第一个球。

之后 K 操作,让黑球位于 x从左边算起第一个位置。求出期望值 x,模数 998244353.

期望值模是多少 998244353? 可以证明,所求的期望值永远是有理数。另外,在这个问题的约束下,可以证明,如果这个值表示为不可约分数 \frac{P}{Q},那么 Q \not \equiv 0 \pmod{998244353}。因此,存在唯一的整数 R 这样 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353。报告此事 R.

约束

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

输入

输入由标准输入按以下格式给出:

N K

输出

在一行中打印答案。


示例输入 1

2 1

示例输出 1

499122178

经过一次操作,黑球位于左起第1个位置和左起第2个位置的概率均为 \displaystyle \frac{1}{2}。因此,期望值为 \displaystyle \frac{3}{2}.


示例输入 2

3 2

示例输出 2

554580198

示例输入 3

4 4

示例输出 3

592707587