Problem H: Count Words
Problem
$M$ 種類の文字がある。それらを使って長さ $N$ の文字列を作る。使われている文字の種類数が $K$ 以上であるような文字列は何通りあるか。$998244353$ で割ったあまりを求めよ。
ここで長さ $N$ の2つの文字列が異なるとは以下のように定義される。
-
2つの文字列を $S = S_1S_2 \ldots S_N$, $T = T_1T_2 \ldots T_N$ とした場合に、$S_i \neq T_i$ となるような $i$ $(1 \leq i \leq N)$ が存在する。
Input
入力は以下の形式で与えられる。
$M$ $N$ $K$
1行に $M, N, K$ が空白区切りで与えられる。
Constraints
入力は以下の条件を満たす。
- $1 \leq M \leq 10^{18} $
- $1 \leq N \leq 10^{18} $
- $1 \leq K \leq 1000 $
- 入力はすべて整数
Output
使われている文字の種類数が $K$ 以上であるような長さ $N$ の文字列の通り数を $998244353$ で割ったあまりを出力せよ。
Sample Input 1
2 10 1
Sample Output 1
1024
Sample Input 2
1 1 2
Sample Output 2
0
Sample Input 3
5 10 3
Sample Output 3
9755400
Sample Input 4
7 8 3
Sample Output 4
5759460
Sample Input 5
1000000000000000000 1000000000000000000 1000
Sample Output 5
133611974