← 返回题目列表

AtCoder · arc172_b

B. AtCoder 语言

中文机器翻译题面 查看原题

分数: 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