[CTS2019] 珍珠
题目背景
白云苍狗,沧海桑田。
白云的眼前只剩下了模糊的一片。
在若隐若现之中,它看到了一个个小小的珍珠,有一些发着五彩的光芒。这些珍珠是白兔留下来的,每颗珍珠有一个颜色,为 $D$ 种颜色中随机的一种。
白云想把这些珍珠放进一些小瓶子中,每个瓶子能恰好容纳两颗珍珠。不过它也有要求,每个瓶子必须装满,并且装的都是相同颜色的珍珠。
白云希望能得到至少 $m$ 个装满珍珠的瓶子,它想知道它的愿望能被实现的概率是多少呢?
题目描述
有 $n$ 个在范围 $[1,D]$ 内的整数均匀随机变量。
求至少能选出 $m$ 个瓶子,使得存在一种方案,选择一些变量,并把选出来的每一个变量放到一个瓶子中,满足每个瓶子都恰好装两个值相同的变量的概率。
请输出概率乘上 $D^n$ 后对 $998244353$ 取模的值。取模部分说明可参考第一题。
输入输出格式
输入格式
输入仅一行,三个用空格隔开的整数 $D,n,m$。
输出格式
输出一个整数,表示所求概率乘上 $D^n$ 后对 $998244353$ 取模的结果。
输入输出样例
输入样例 #1
2 2 1
输出样例 #1
2
输入样例 #2
8 10 4
输出样例 #2
301103104
输入样例 #3
998 1000 500
输出样例 #3
762913089
说明
#### 样例 1 解释
情况 $1$ : 第一个变量为 $1$,第二个变量为 $1$
情况 $2$ : 第一个变量为 $1$,第二个变量为 $2$
情况 $3$ : 第一个变量为 $2$,第二个变量为 $1$
情况 $4$ : 第一个变量为 $2$,第二个变量为 $2$
其中情况 $1$ 和 $4$ 可以把两个变量放到一个瓶子中
情况 $2$ 和 $3$ 中两个变量的值不相同,所以不能放到同一个瓶子中
#### 测试数据约定
![img](https://s2.ax1x.com/2019/05/17/Eq683D.png)
所有测试点均满足 $0 \leqslant m \leqslant 10^9,1 \leqslant n \leqslant 10^9,1 \leqslant D \leqslant 10^5$。