#3120. 「CTS2019 | CTSC2019」珍珠

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

输入格式

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

输出格式

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

样例

样例输入 1

2 2 1

样例输出 1

2

样例解释 1

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

样例 2

见附加文件中的 pearl2.inpearl2.ans

样例 3

见附加文件中的 pearl3.inpearl3.ans

数据范围与提示

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

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