Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import bisect
import collections
import sys
import functools
import math

sys.setrecursionlimit(100000000)
ACMOD = 1000000007
INF = 1 << 62

MOD = 998244353  # type: int


@functools.lru_cache(maxsize=None)
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def solve(N: int, M: int, K: int):
    if N == 1:
        print(M)
        exit()
    #
    # @functools.lru_cache(maxsize=None)
    # def f(i, k):
    #     if k < 0:
    #         return 0
    #     if i == N - 1:
    #         return M - 1 if k == 0 else M
    #     if i == 0:
    #         return M * f(i + 1, k)
    #     # diff color + same color
    #     return (M - 1) * f(i + 1, k) + f(i + 1, k - 1)
    #
    # print(f(0, K)%MOD)
    n = N - 1
    nCr = 1
    _sum = 0
    # (M - 1) ** (N - k - 1)
    e = [1]
    for i in range(N):
        e.append(e[-1] * (M - 1) % MOD)
    # print('ok')
    for k in range(K + 1):
        # print(nCr)
        _sum += M * e[N - k - 1] * nCr % MOD
        # print(nCr%MOD, comb(N - 1, k)%MOD)
        nCr = nCr * (n - k) // (k + 1)

    print(_sum % MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int

    solve(N, M, K)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import bisect
import collections
import sys
import functools
import scipy
import math

sys.setrecursionlimit(100000000)
ACMOD = 1000000007
INF = 1 << 62

MOD = 998244353  # type: int

# def comb(n, r):
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

from operator import mul
from functools import reduce


def modinv(a,*args):
    return pow(a, MOD - 2, MOD)

def combination_list(n, mod=MOD):
    lst = [1]
    for i in range(1, n+1):
        lst.append(lst[-1] * (n+1-i) % mod * modinv(i, mod) % mod)
    return lst


def comb(n, r):
    r = min(n - r, r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


def solve(N: int, M: int, K: int):
    if N == 1:
        print(M)
        exit()
    #
    # @functools.lru_cache(maxsize=None)
    # def f(i, k):
    #     if k < 0:
    #         return 0
    #     if i == N - 1:
    #         return M - 1 if k == 0 else M
    #     if i == 0:
    #         return M * f(i + 1, k)
    #     # diff color + same color
    #     return (M - 1) * f(i + 1, k) + f(i + 1, k - 1)
    #
    # print(f(0, K)%MOD)
    n = N - 1
    nCr = 1
    _sum = 0
    # (M - 1) ** (N - k - 1)
    e = [1]
    for i in range(N):
        e.append(e[-1] * (M - 1) % MOD)
    # print('ok')
    nCrArr = combination_list(n,MOD)
    for k in range(K + 1):
        # print(nCr)
        # nCr = cmb(N - 1, k)%MOD
        _sum += M * e[N - k - 1] * nCrArr[k] % MOD
        # print(nCr%MOD, comb(N - 1, k)%MOD)
        # nCr = nCr * (n - k) // (k + 1) * modinv(k ) % MOD
        # nCr= nCr%MOD
    print(_sum % MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int

    solve(N, M, K)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import bisect
import collections
import sys
import functools
import math

sys.setrecursionlimit(100000000)
ACMOD = 1000000007
INF = 1 << 62

MOD = 998244353  # type: int


@functools.lru_cache(maxsize=None)
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def solve(N: int, M: int, K: int):
    if N == 1:
        print(M)
        exit()
    #
    # @functools.lru_cache(maxsize=None)
    # def f(i, k):
    #     if k < 0:
    #         return 0
    #     if i == N - 1:
    #         return M - 1 if k == 0 else M
    #     if i == 0:
    #         return M * f(i + 1, k)
    #     # diff color + same color
    #     return (M - 1) * f(i + 1, k) + f(i + 1, k - 1)
    #
    # print(f(0, K)%MOD)
    n = N - 1
    nCr = 1
    _sum = 0
    # (M - 1) ** (N - k - 1)
    e = [1]
    for i in range(N):
        e.append(e[-1] * (M - 1) % MOD)
    # print('ok')
    for k in range(K + 1):
        # print(nCr)
        _sum += M * e[N - k - 1] * nCr
        # print(nCr%MOD, comb(N - 1, k)%MOD)
        nCr = nCr * (n - k) // (k + 1)

    print(_sum % MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int

    solve(N, M, K)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import bisect
import collections
import sys
import functools
import scipy
import math

sys.setrecursionlimit(100000000)
ACMOD = 1000000007
INF = 1 << 62

MOD = 998244353  # type: int

# def comb(n, r):
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

from operator import mul
from functools import reduce


def modinv(a,*args):
    return pow(a, MOD - 2, MOD)

def combination_list(n, mod=MOD):
    lst = [1]
    for i in range(1, n+1):
        lst.append(lst[-1] * (n+1-i) % mod * modinv(i, mod) % mod)
    return lst


def comb(n, r):
    r = min(n - r, r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


def solve(N: int, M: int, K: int):
    if N == 1:
        print(M)
        exit()
    #
    # @functools.lru_cache(maxsize=None)
    # def f(i, k):
    #     if k < 0:
    #         return 0
    #     if i == N - 1:
    #         return M - 1 if k == 0 else M
    #     if i == 0:
    #         return M * f(i + 1, k)
    #     # diff color + same color
    #     return (M - 1) * f(i + 1, k) + f(i + 1, k - 1)
    #
    # print(f(0, K)%MOD)
    n = N - 1
    nCr = 1
    _sum = 0
    # (M - 1) ** (N - k - 1)
    e = [1]
    for i in range(N):
        e.append(e[-1] * (M - 1) % MOD)
    # print('ok')
    nCrArr = combination_list(n,MOD)
    for k in range(K + 1):
        # print(nCr)
        # nCr = cmb(N - 1, k)%MOD
        _sum += M * e[N - k - 1] * nCrArr[k] % MOD
        # print(nCr%MOD, comb(N - 1, k)%MOD)
        # nCr = nCr * (n - k) // (k + 1) * modinv(k ) % MOD
        # nCr= nCr%MOD
    print(_sum % MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int

    solve(N, M, K)


if __name__ == '__main__':
    main()