B - AtCoder Language Editorial /

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