Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
AtCoder 語には L 種類の文字があります。 AtCoder 語の文字からなる N 文字の文字列 s のうち、以下の条件を満たすものは何通りありますか。 答えを 998244353 で割った余りを求めてください。
- 文字列 s のどの「K 文字の部分列」も異なる。厳密には、文字列 s から K 文字を抜き出し、そのままの順序で連結して K 文字の文字列を得る方法は _N\mathrm{C}_K 通りあるが、それらすべてが異なる文字列を生成する。
_N\mathrm{C}_K とは
N 個のものの中から K 個を選ぶ方法の総数を指します。より厳密には、_N\mathrm{C}_K は N! を K! \times (N-K)! で割った値です。制約
- 1 \leq K < N \leq 500000
- 1 \leq L \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N K L
出力
答えを出力してください。
入力例 1
4 3 2
出力例 1
2
AtCoder 語の 1 種類目の文字を a
、2 種類目の文字を b
と表すとき、条件を満たす文字列は abab
、baba
の 2 通りとなります。
入力例 2
100 80 26
出力例 2
496798269
条件を満たす文字列はおよそ 10^{86} 通りありますが、ここでは 998244353 で割った余りである 496798269 を出力します。
入力例 3
100 1 26
出力例 3
0
入力例 4
500000 172172 503746693
出力例 4
869120
Score: 500 points
Problem Statement
The AtCoder language has L different characters. How many N-character strings s consisting of characters in the AtCoder language satisfy the following condition? Find the count modulo 998244353.
- All K-character subsequences of the string s are different. More precisely, there are _N\mathrm{C}_K ways to obtain a K-character string by extracting K characters from the string s and concatenating them without changing the order, and all of these ways must generate different strings.
What is _N\mathrm{C}_K?
_N\mathrm{C}_K refers to the total number of ways to choose K from N items. More precisely, _N\mathrm{C}_K is the value of N! divided by K! \times (N-K)!.Constraints
- 1 \leq K < N \leq 500000
- 1 \leq L \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K L
Output
Print the count modulo 998244353.
Sample Input 1
4 3 2
Sample Output 1
2
If a
and b
represent the first and second characters in the language, the condition is satisfied by two strings: abab
and baba
.
Sample Input 2
100 80 26
Sample Output 2
496798269
Approximately 10^{86} strings satisfy the condition, but here we print the count modulo 998244353, which is 496798269.
Sample Input 3
100 1 26
Sample Output 3
0
Sample Input 4
500000 172172 503746693
Sample Output 4
869120