Buggy python submission (verdict: Time Limit Exceeded):
n, m, k = map(int, input().split())
MOD = 998244353


def power(n, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 1:
        return (n * power(n, k - 1, mod)) % mod
    else:
        return power((n ** 2) % mod, k // 2, mod)


lp = [1]  # (m - 1) ** i
p = 1
for i in range(n - 1):
    p = (p * (m - 1)) % MOD
    lp.append(p)


lf = [1]  # i!
f = 1
for i in range(n - 1):
    f = (f * (i + 1)) % MOD
    lf.append(f)

fn = lf[-1]

answer = 0

for i, f, fr, p in zip(range(k + 1), lf, reversed(lf), reversed(lp)):
    # d = (lf[i] * lf[n - 1 - i]) % MOD
    d = (f * fr) % MOD
    dinv = power(d, MOD - 2, MOD)
    c = (fn * dinv) % MOD
    # n_pattern = (c * m * lp[n - 1 - i]) % MOD
    n_pattern = (c * m * p) % MOD

    answer = (answer + n_pattern) % MOD


print(answer)






Fixed submission:
n, m, k = map(int, input().split())
MOD = 998244353


class Combination:
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod

        self.f = self._get_f()
        self.fi = self._get_fi()

    def __call__(self, k):
        if not 0 <= k <= self.n:
            return 0
        else:
            num = self.f[self.n]
            deninv = (self.fi[k] * self.fi[self.n - k]) % self.mod
            return (num * deninv) % self.mod

    def _get_f(self):
        f = 1
        lf = [1]

        for i in range(1, self.n + 1):
            f = (f * i) % self.mod
            lf.append(f)

        return lf

    def _get_fi(self):
        ii = 1
        lii = [0, 1]  # [i^-1 modulo mod for i in 0, ..., n]
        fi = 1
        lfi = [1, 1]

        for i in range(2, self.n + 1):
            ii = (-lii[self.mod % i] * (self.mod // i)) % self.mod
            lii.append(ii)

            fi = (fi * ii) % self.mod
            lfi.append(fi)

        return lfi


c = Combination(n - 1, MOD)


def n_pattern(i):
    result = m
    result *= c(i)
    result %= MOD
    result *= pow(m - 1, n - i - 1, MOD)
    result %= MOD
    return result


answer = sum(n_pattern(i) for i in range(k + 1)) % MOD
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n, m, k = map(int, input().split())
MOD = 998244353


def power(n, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 1:
        return (n * power(n, k - 1, mod)) % mod
    else:
        return power((n ** 2) % mod, k // 2, mod)


lp = [1]  # (m - 1) ** i
p = 1
for i in range(n - 1):
    p = (p * (m - 1)) % MOD
    lp.append(p)


lf = [1]  # i!
f = 1
for i in range(n - 1):
    f = (f * (i + 1)) % MOD
    lf.append(f)

fn = lf[-1]

answer = 0

fr = 1
for i in range(n - 1 - (k + 1)):
    fr = (fr * (i + 1)) % MOD


f = 1
for i, f, fr, p in zip(range(k + 1), lf, reversed(lf), reversed(lp)):
    # d = (lf[i] * lf[n - 1 - i]) % MOD
    d = (f * fr) % MOD
    dinv = power(d, MOD - 2, MOD)
    c = (fn * dinv) % MOD
    # n_pattern = (c * m * lp[n - 1 - i]) % MOD
    n_pattern = (c * m * p) % MOD

    answer = (answer + n_pattern) % MOD


# def n_pattern(n_pair):
#     return (lc[n_pair] * m * power(m - 1, n - 1 - n_pair, MOD)) % MOD


# answer = 0
# for i in range(k + 1):
#     answer = (answer + n_pattern(i)) % MOD


print(answer)






Fixed submission:
n, m, k = map(int, input().split())
MOD = 998244353


class Combination:
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod

        self.f = self._get_f()
        self.fi = self._get_fi()

    def __call__(self, k):
        if not 0 <= k <= self.n:
            return 0
        else:
            num = self.f[self.n]
            deninv = (self.fi[k] * self.fi[self.n - k]) % self.mod
            return (num * deninv) % self.mod

    def _get_f(self):
        f = 1
        lf = [1]

        for i in range(1, self.n + 1):
            f = (f * i) % self.mod
            lf.append(f)

        return lf

    def _get_fi(self):
        ii = 1
        lii = [0, 1]  # [i^-1 modulo mod for i in 0, ..., n]
        fi = 1
        lfi = [1, 1]

        for i in range(2, self.n + 1):
            ii = (-lii[self.mod % i] * (self.mod // i)) % self.mod
            lii.append(ii)

            fi = (fi * ii) % self.mod
            lfi.append(fi)

        return lfi


c = Combination(n - 1, MOD)


def n_pattern(i):
    result = m
    result *= c(i)
    result %= MOD
    result *= pow(m - 1, n - i - 1, MOD)
    result %= MOD
    return result


answer = sum(n_pattern(i) for i in range(k + 1)) % MOD
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n, m, k = map(int, input().split())
MOD = 998244353


def power(n, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 1:
        return (n * power(n, k - 1, mod)) % mod
    else:
        return power((n ** 2) % mod, k // 2, mod)


lp = {0: 1}  # (m - 1) ** i
p = 1
for i in range(n - 1):
    p = (p * (m - 1)) % MOD
    lp[i + 1] = p


lf = {0: 1}  # i!
f = 1
for i in range(n):
    f = (f * (i + 1)) % MOD
    lf[i + 1] = f

fn = lf[n - 1]


answer = 0

for i in range(k + 1):
    d = (lf[i] * lf[n - 1 - i]) % MOD
    dinv = power(d, MOD - 2, MOD)
    c = (fn * dinv) % MOD
    n_pattern = (c * m * lp[n - 1 - i]) % MOD

    answer = (answer + n_pattern) % MOD


# def n_pattern(n_pair):
#     return (lc[n_pair] * m * power(m - 1, n - 1 - n_pair, MOD)) % MOD


# answer = 0
# for i in range(k + 1):
#     answer = (answer + n_pattern(i)) % MOD


print(answer)






Fixed submission:
n, m, k = map(int, input().split())
MOD = 998244353


class Combination:
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod

        self.f = self._get_f()
        self.fi = self._get_fi()

    def __call__(self, k):
        if not 0 <= k <= self.n:
            return 0
        else:
            num = self.f[self.n]
            deninv = (self.fi[k] * self.fi[self.n - k]) % self.mod
            return (num * deninv) % self.mod

    def _get_f(self):
        f = 1
        lf = [1]

        for i in range(1, self.n + 1):
            f = (f * i) % self.mod
            lf.append(f)

        return lf

    def _get_fi(self):
        ii = 1
        lii = [0, 1]  # [i^-1 modulo mod for i in 0, ..., n]
        fi = 1
        lfi = [1, 1]

        for i in range(2, self.n + 1):
            ii = (-lii[self.mod % i] * (self.mod // i)) % self.mod
            lii.append(ii)

            fi = (fi * ii) % self.mod
            lfi.append(fi)

        return lfi


c = Combination(n - 1, MOD)


def n_pattern(i):
    result = m
    result *= c(i)
    result %= MOD
    result *= pow(m - 1, n - i - 1, MOD)
    result %= MOD
    return result


answer = sum(n_pattern(i) for i in range(k + 1)) % MOD
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n, m, k = map(int, input().split())
MOD = 998244353


def power(n, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 1:
        return (n * power(n, k - 1, mod)) % mod
    else:
        return power((n ** 2) % mod, k // 2, mod)


lp = [1]  # (m - 1) ** i
p = 1
for i in range(n - 1):
    p = (p * (m - 1)) % MOD
    lp.append(p)


lf = [1]  # i!
f = 1
for i in range(n - 1):
    f = (f * (i + 1)) % MOD
    lf.append(f)

fn = lf[-1]


# lc = []  # n - 1 C i
answer = 0
for i in range(k + 1):
    d = (lf[i] * lf[n - 1 - i]) % MOD
    dinv = power(d, MOD - 2, MOD)
    c = (fn * dinv) % MOD
    # lc.append(c)
    n_pattern = (c * m * lp[n - 1 - i]) % MOD

    answer = (answer + n_pattern) % MOD


# def n_pattern(n_pair):
#     return (lc[n_pair] * m * power(m - 1, n - 1 - n_pair, MOD)) % MOD


# answer = 0
# for i in range(k + 1):
#     answer = (answer + n_pattern(i)) % MOD


print(answer)






Fixed submission:
n, m, k = map(int, input().split())
MOD = 998244353


class Combination:
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod

        self.f = self._get_f()
        self.fi = self._get_fi()

    def __call__(self, k):
        if not 0 <= k <= self.n:
            return 0
        else:
            num = self.f[self.n]
            deninv = (self.fi[k] * self.fi[self.n - k]) % self.mod
            return (num * deninv) % self.mod

    def _get_f(self):
        f = 1
        lf = [1]

        for i in range(1, self.n + 1):
            f = (f * i) % self.mod
            lf.append(f)

        return lf

    def _get_fi(self):
        ii = 1
        lii = [0, 1]  # [i^-1 modulo mod for i in 0, ..., n]
        fi = 1
        lfi = [1, 1]

        for i in range(2, self.n + 1):
            ii = (-lii[self.mod % i] * (self.mod // i)) % self.mod
            lii.append(ii)

            fi = (fi * ii) % self.mod
            lfi.append(fi)

        return lfi


c = Combination(n - 1, MOD)


def n_pattern(i):
    result = m
    result *= c(i)
    result %= MOD
    result *= pow(m - 1, n - i - 1, MOD)
    result %= MOD
    return result


answer = sum(n_pattern(i) for i in range(k + 1)) % MOD
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n, m, k = map(int, input().split())
MOD = 998244353


def power(n, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 1:
        return (n * power(n, k - 1, mod)) % mod
    else:
        return power((n ** 2) % mod, k // 2, mod)


lf = [1]  # k!
f = 1
for i in range(n - 1):
    f = (f * (i + 1)) % MOD
    lf.append(f)

fn = lf[-1]


lc = []  # n - 1 C i
for i in range(n):
    d = (lf[i] * lf[n - 1 - i]) % MOD
    dinv = power(d, MOD - 2, MOD)
    c = (fn * dinv) % MOD
    lc.append(c)


def n_pattern(n_pair):
    return (lc[n_pair] * m * power(m - 1, n - 1 - n_pair, MOD)) % MOD


answer = 0
for i in range(k + 1):
    answer += n_pattern(i)


print(answer % MOD)






Fixed submission:
n, m, k = map(int, input().split())
MOD = 998244353


class Combination:
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod

        self.f = self._get_f()
        self.fi = self._get_fi()

    def __call__(self, k):
        if not 0 <= k <= self.n:
            return 0
        else:
            num = self.f[self.n]
            deninv = (self.fi[k] * self.fi[self.n - k]) % self.mod
            return (num * deninv) % self.mod

    def _get_f(self):
        f = 1
        lf = [1]

        for i in range(1, self.n + 1):
            f = (f * i) % self.mod
            lf.append(f)

        return lf

    def _get_fi(self):
        ii = 1
        lii = [0, 1]  # [i^-1 modulo mod for i in 0, ..., n]
        fi = 1
        lfi = [1, 1]

        for i in range(2, self.n + 1):
            ii = (-lii[self.mod % i] * (self.mod // i)) % self.mod
            lii.append(ii)

            fi = (fi * ii) % self.mod
            lfi.append(fi)

        return lfi


c = Combination(n - 1, MOD)


def n_pattern(i):
    result = m
    result *= c(i)
    result %= MOD
    result *= pow(m - 1, n - i - 1, MOD)
    result %= MOD
    return result


answer = sum(n_pattern(i) for i in range(k + 1)) % MOD
print(answer)