AT_abc360_e Random Swaps of Balls

题目描述

有 $N - 1$ 个白球和 $1$ 个黑球。这 $N$ 个球排成一列，初始时黑球在最左边。

高桥君将执行以下操作恰好 $K$ 次：

• 进行两次试验，每次试验均匀随机选择一个 $1$ 到 $N$ 之间的整数。设选出的整数分别为 $a$ 和 $b$。如果 $a \neq b$，则交换从左边数第 $a$ 个球和第 $b$ 个球。

设 $K$ 次操作后，黑球在从左边数第 $x$ 个位置。请计算 $x$ 的期望值，并将结果对 $998244353$ 取模。

期望值 $\text{mod}\ 998244353$ 是指：可以证明所求的期望值一定是有理数。此外，在这个问题的约束条件下，可以证明当这个值表示成既约分数 $\frac{P}{Q}$ 时，$Q \not\equiv 0 \pmod{998244353}$。因此，存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$，且 $0 \leq R < 998244353$。请输出这个 $R$。

输入格式

输入从标准输入中给出，格式为一行两个整数：

$N$ $K$

输出格式

答案于第一行输出。

输入输出样例 #1

输入 #1

2 1

输出 #1

499122178

输入输出样例 #2

输入 #2

3 2

输出 #2

554580198

输入输出样例 #3

输入 #3

4 4

输出 #3

592707587

说明/提示

约束条件

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

样例解释 1

完成 $1$ 次操作后，黑球位于从左边数第 $1$ 个位置的概率和位于第 $2$ 个位置的概率都是 $\frac{1}{2}$。因此，期望值为 $\frac{3}{2}$。