#P18036. Ball Dumping Golf

Ball Dumping Golf

Ball Dumping Golf

题目描述

有 NN 个盒子,编号为 1,…,N1,\ldots,N。每个编号都有 MM 个带有该编号的小球,共 NMNM 个球。

将全部球打乱,放入这些盒子,使每个盒子恰好装有 MM 个球。如果把所有球都视为可区分的个体,那么共有 (NM)!(M!)N\frac{(NM)!}{(M!)^N} 种放置方式,每种方式等概率出现。特别地,同一编号的球在计算随机分布时仍视为不同个体。

你可以进行操作,每次操作包含以下步骤:

  1. 任选一个盒子,走到它面前。
  2. 如果当前盒子为空,本次操作结束。
  3. 否则,任选当前盒子里的一个球,将它丢弃。
  4. 走到编号等于刚刚丢弃的小球编号的盒子面前,返回步骤 2。

所有球都被丢弃时,所进行的操作次数就是得分。对于每一种初始放置方式,你都采取使得分最小的最优策略。

求这个最小得分的期望,对 998244353998244353 取模。

期望可以写成最简分数 y/xy/x,题目保证 xx 不被 998244353998244353 整除。需要输出唯一的整数 z∈[0,998244352]z\in[0,998244352],使 xz≡y(mod998244353)xz\equiv y\pmod{998244353}。

输入格式

一行两个整数 N,MN,M。

1≤N≤1051\le N\le10^5,1≤M≤1001\le M\le100。

输出格式

输出期望值对 998244353998244353 取模的结果。

样例 1

输入:

2 2

输出:

166374060

样例 2

输入:

3 1

输出:

831870296

样例 3

输入:

100000 100

输出:

402978825

样例 1 中,最优得分为 2 的概率为 1/61/6,为 1 的概率为 5/65/6,期望为 7/67/6。