[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$。