C0127 [CTSC2019]珍珠

内存限制:512 MB 时间限制:1000 ms

题目描述

白云苍狗,沧海桑田。

白云的眼前只剩下了模糊的一片。

在若隐若现之中,它看到了一个个小小的珍珠,有一些发着五彩的光芒。这些珍珠是白兔留下来的,每颗珍珠有一个颜色,为 $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 中两个变量的值不相同,所以不能放到同一个瓶子中

【测试数据约定】

屏幕快照 2019-07-09 下午3.53.29.png

所有测试点均满足 $0⩽m⩽10^9,1⩽n⩽10^9,1⩽D⩽10^5$。