分数: 500 点
问题陈述
AtCoder 语言有 L 不同的字符。 有多少 N- 字符串 s 由AtCoder语言中的字符组成,满足以下条件吗? 求计数模数 998244353.
- 全部 K- 字符串的字符子序列 s 不同。更准确地说,有 _N\mathrm{C}_K 获得方法 K- 提取的字符串 字符串中的 K 个字符 s 并在不改变顺序的情况下连接它们,所有这些方式都必须生成不同的字符串。
什么是 _N\mathrm{C}_K?
_N\mathrm{C}_K 指选择的方式总数 K 来自 N 项目。更准确地说, _N\mathrm{C}_K 的值 N! 除以 K! \times (N-K)!.约束
- 1 \leq K < N \leq 500000
- 1 \leq L \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K L
输出
打印计数模数 998244353.
示例输入 1
4 3 2
示例输出 1
2
If a 和 b 代表语言中的第一个和第二个字符,两个字符串满足条件: abab 和 baba.
示例输入 2
100 80 26
示例输出 2
496798269
大约 10^{86} 字符串满足条件,但这里我们打印计数模 998244353,即 496798269.
示例输入 3
100 1 26
示例输出 3
0
示例输入 4
500000 172172 503746693
示例输出 4
869120