3120 「CTS2019 | CTSC2019」珍珠

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

题目描述

白云苍狗,沧海桑田。
白云的眼前只剩下了模糊的一片。
在若隐若现之中,它看到了一个个小小的珍珠,有一些发着五彩的光芒。这些珍珠是白兔留下来的,每颗珍珠有一个颜色,为 $D$ 种颜色中随机的一种。
白云想把这些珍珠放进一些小瓶子中,每个瓶子能恰好容纳两颗珍珠。不过它也有要求,每个瓶子必须装满,并且装的都是相同颜色的珍珠。
白云希望能得到至少 $m$ 个装满珍珠的瓶子,它想知道它的愿望能被实现的概率是多少呢?

有 $n$ 个在范围 $[1,D]$ 内的整数均匀随机变量。
求至少能选出 $m$ 个瓶子,使得存在一种方案,选择一些变量,并把选出来的每一个变量放到一个瓶子中,满足每个瓶子都恰好装两个值相同的变量的概率。
请输出概率乘上 $D^n$ 后对 $998244353$ 取模的值。取模部分说明可参考第一题(随机立方体)。

输入格式

输入仅一行,三个用空格隔开的整数 $D,n,m$。

输出格式

输出一个整数,表示所求概率乘上 $D^n$ 后对 $998244353$ 取模的结果。

样例

情况 $1$ : 第一个变量为 $1$,第二个变量为 $1$ 情况 $2$ : 第一个变量为 $1$,第二个变量为 $2$ 情况 $3$ : 第一个变量为 $2$,第二个变量为 $1$ 情况 $4$ : 第一个变量为 $2$,第二个变量为 $2$ 其中情况 $1$ 和 $4$ 可以把两个变量放到一个瓶子中 情况 $2$ 和 $3$ 中两个变量的值不相同,所以不能放到同一个瓶子中

见附加文件中的 pearl2.in 与 pearl2.ans。

见附加文件中的 pearl3.in 与 pearl3.ans。

数据范围与提示

测试点编号 $D$ $n$ $m$
$1$ $\le 2$ $\le 10$ $\le n$
$2$ $\le 2$ $\le 20$ $\le n$
$3$ $\le 100$ $\le 100$ $\le n$
$4$ $\le 100$ $\le 100$ $\le n$
$5$ $\le 100$ $\le 100$ $\le n$
$6$ $\le 100$ $\le 100$ $\le n$
$7$ $\le 100$ $\le 100$ $\le n$
$8$ $\le 4000$ $\le 4000$ $\le n$
$9$ $\le 4000$ $\le 4000$ $\le n$
$10$ $\le 4000$ $\le 4000$ $\le n$
$11$ $\le 4000$ $\le 4000$ $\le n$
$12$ $\le 4000$ $\le 4000$ $\le n$
$13$ $\le 300$ $\le 1000000000$ $\le n$
$14$ $\le 300$ $\le 1000000000$ $\le n$
$15$ $\le 300$ $\le 1000000000$ $\le n$
$16$ $\le 100000$ $\le 1000000000$ $\le 0$
$17$ $\le 100000$ $\le 1000000000$ $\le 1$
$18$ $\le 100000$ $\le 1000000000$ $\le 2$
$19$ $\le 100000$ $\le 1000000000$ $\le n$
$20$ $\le 100000$ $\le 1000000000$ $\le n$
$21$ $\le 100000$ $\le 1000000000$ $\le n$
$22$ $\le 100000$ $\le 1000000000$ $\le n$
$23$ $\le 100000$ $\le 1000000000$ $\le n$
$24$ $\le 100000$ $\le 1000000000$ $\le n$
$25$ $\le 100000$ $\le 1000000000$ $\le n$

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

样例

样例输入 1

2 2 1

样例输出 1

2