Problem:

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



Sample input:
2 10 1


Sample output:
1024

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 998244353


def solve():
    m,n,k = LI()
    if n < k:
        print(0)
        return
    if m < k:
        print(0)
        return
    ans = pow(m,n,mod)
    p = [pow(i,n,mod) for i in range(k+1)]
    c = m
    comb = [[0 for i in range(i+1)] for i in range(k+1)]
    comb[0][0] = 1
    for i in range(k):
        for j in range(i+1):
            comb[i+1][j] += comb[i][j]
            comb[i+1][j+1] += comb[i][j]
    for i in range(1,k):
        k = 0
        for j in range(1,i+1)[::-1]:
            if (i+j)&1:
                k -= comb[i][j]*p[j]
            else:
                k += comb[i][j]*p[j]
        k *= c
        c *= (m-i)
        c *= pow(i+1,mod-2,mod)
        c %= mod
        ans -= k
        ans %= mod
    print(ans)
    return


if __name__ == "__main__":
    solve()