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

---