分数: 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