Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)


class ModInt(int):
    
    MOD = 998244353

    def __new__(cls, x, *args, **kwargs):
        return super().__new__(cls, x % ModInt.MOD)

    def __add__(self, other):
        return ModInt(super().__add__(other) % ModInt.MOD)

    def __radd__(self, other):
        return ModInt(super().__radd__(other) % ModInt.MOD)

    def __mul__(self, other):
        return ModInt(super().__mul__(other) % ModInt.MOD)

    def __rmul__(self, other):
        return ModInt(super().__rmul__(other) % ModInt.MOD)

    def __pow__(self, other, *args):
        return ModInt(super().__pow__(other, ModInt.MOD))

    def __rpow__(self, other, *args):
        raise NotImplementedError()

    def __truediv__(self, other):
        inv = ModInt(other).inverse()
        return ModInt(super().__mul__(inv) % ModInt.MOD)

    def __floordiv__(self, other):
        return self.__truediv__(other)

    def __rtruediv__(self, other):
        return ModInt(self.inverse().__mul__(other))

    def __rfloordiv__(self, other):
        return self.__rtruediv__(other)

    def _extgcd(self, a, b):
        assert not isinstance(a, ModInt) and not isinstance(b, ModInt)
        if a < b:
            m, y, x = self._extgcd(b, a)
            return (m, x, y)
        if b == 0:
            x = 1
            y = 0
            return (a, x, y)
        m, y, x = self._extgcd(b, a % b)
        y = y - a // b * x
        return (m, x, y)

    def inverse(self):
        a = int(self)
        m = int(ModInt.MOD)
        n, x, y = self._extgcd(a, m)
        if n != 1:
            raise ValueError("{} and {} are not mutually prime.".format(a, m))
        return ModInt(x)


def read():
    N, M, K = map(int, input().strip().split())
    return N, M, K


# 998244353は素数
def solve(N, M, K, MOD=998244353):
    # dp[n、k] = nブロック、組k以下での彩色パターン数
    dp = [[ModInt(0) for j in range(K+1)] for i in range(2)]
    dp[0][K] = ModInt(1)
    for i in range(N):
        j0 = i % 2
        j1 = (i+1) % 2
        for k in range(K, max(K-i, -1), -1):
            dp[j1][k] = ModInt(0)
        for k in range(K, -1, -1):
            if i == 0:
                dp[j1][k] += M * dp[j0][k]
            else:
                if k > 0:
                    dp[j1][k-1] += 1 * dp[j0][k]
                dp[j1][k] += (M-1) * dp[j0][k]
    ans = ModInt(0)
    for k in range(K+1):
        ans += dp[N % 2][k]
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)


def binom_preprocess(n, MOD=998244353):
    f = [0 for i in range(n+1)]  # n!
    invf = [0 for i in range(n+1)]  # (n!)^-1
    f[0] = 1
    f[1] = 1
    invf[0] = 1
    invf[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] * i % MOD
        invf[i] = pow(f[i], MOD-2, MOD)
    return f, invf


def binom(n, k, f, invf, MOD=998244353):
    if n < k or n < 0 or k < 0:
        return 0
    else:
        return (f[n] * invf[k] % MOD) * invf[n-k] % MOD


def read():
    N, M, K = map(int, input().strip().split())
    return N, M, K


# 998244353は素数
def solve(N, M, K, MOD=998244353):
    ans = 0
    f, invf = binom_preprocess(N)
    for k in range(K+1):
        ans += binom(N-1, N-k-1, f, invf) * M * pow(M-1, N-k-1, MOD)
        ans %= MOD
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)


class ModInt(int):
    
    MOD = 998244353

    def __new__(cls, x, *args, **kwargs):
        return super().__new__(cls, x % ModInt.MOD)

    def __add__(self, other):
        return ModInt(super().__add__(other) % ModInt.MOD)

    def __radd__(self, other):
        return ModInt(super().__radd__(other) % ModInt.MOD)

    def __mul__(self, other):
        return ModInt(super().__mul__(other) % ModInt.MOD)

    def __rmul__(self, other):
        return ModInt(super().__rmul__(other) % ModInt.MOD)

    def __pow__(self, other, *args):
        return ModInt(super().__pow__(other, ModInt.MOD))

    def __rpow__(self, other, *args):
        raise NotImplementedError()

    def __truediv__(self, other):
        inv = ModInt(other).inverse()
        return ModInt(super().__mul__(inv) % ModInt.MOD)

    def __floordiv__(self, other):
        return self.__truediv__(other)

    def __rtruediv__(self, other):
        return ModInt(self.inverse().__mul__(other))

    def __rfloordiv__(self, other):
        return self.__rtruediv__(other)

    def _extgcd(self, a, b):
        assert not isinstance(a, ModInt) and not isinstance(b, ModInt)
        if a < b:
            m, y, x = self._extgcd(b, a)
            return (m, x, y)
        if b == 0:
            x = 1
            y = 0
            return (a, x, y)
        m, y, x = self._extgcd(b, a % b)
        y = y - a // b * x
        return (m, x, y)

    def inverse(self):
        a = int(self)
        m = int(ModInt.MOD)
        n, x, y = self._extgcd(a, m)
        if n != 1:
            raise ValueError("{} and {} are not mutually prime.".format(a, m))
        return ModInt(x)


def read():
    N, M, K = map(int, input().strip().split())
    return N, M, K


# 998244353は素数
def solve(N, M, K, MOD=998244353):
    # dp[n、k] = nブロック、組k以下での彩色パターン数
    dp = [[ModInt(0) for j in range(K+1)] for i in range(2)]
    dp[0][K] = ModInt(1)
    for i in range(N):
        j0 = i % 2
        j1 = (i+1) % 2
        for k in range(K, -1, -1):
            dp[j1][k] = ModInt(0)
        for k in range(K, -1, -1):
            if i == 0:
                dp[j1][k] += M * dp[j0][k]
            else:
                if k > 0:
                    dp[j1][k-1] += 1 * dp[j0][k]
                dp[j1][k] += (M-1) * dp[j0][k]
    ans = ModInt(0)
    for k in range(K+1):
        ans += dp[N % 2][k]
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)


def binom_preprocess(n, MOD=998244353):
    f = [0 for i in range(n+1)]  # n!
    invf = [0 for i in range(n+1)]  # (n!)^-1
    f[0] = 1
    f[1] = 1
    invf[0] = 1
    invf[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] * i % MOD
        invf[i] = pow(f[i], MOD-2, MOD)
    return f, invf


def binom(n, k, f, invf, MOD=998244353):
    if n < k or n < 0 or k < 0:
        return 0
    else:
        return (f[n] * invf[k] % MOD) * invf[n-k] % MOD


def read():
    N, M, K = map(int, input().strip().split())
    return N, M, K


# 998244353は素数
def solve(N, M, K, MOD=998244353):
    ans = 0
    f, invf = binom_preprocess(N)
    for k in range(K+1):
        ans += binom(N-1, N-k-1, f, invf) * M * pow(M-1, N-k-1, MOD)
        ans %= MOD
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)


class ModInt(int):
    
    MOD = 998244353

    def __new__(cls, x, *args, **kwargs):
        return super().__new__(cls, x % ModInt.MOD)

    def __add__(self, other):
        return ModInt(super().__add__(other) % ModInt.MOD)

    def __radd__(self, other):
        return ModInt(super().__radd__(other) % ModInt.MOD)

    def __mul__(self, other):
        return ModInt(super().__mul__(other) % ModInt.MOD)

    def __rmul__(self, other):
        return ModInt(super().__rmul__(other) % ModInt.MOD)

    def __pow__(self, other, *args):
        return ModInt(super().__pow__(other, ModInt.MOD))

    def __rpow__(self, other, *args):
        raise NotImplementedError()

    def __truediv__(self, other):
        inv = ModInt(other).inverse()
        return ModInt(super().__mul__(inv) % ModInt.MOD)

    def __floordiv__(self, other):
        return self.__truediv__(other)

    def __rtruediv__(self, other):
        return ModInt(self.inverse().__mul__(other))

    def __rfloordiv__(self, other):
        return self.__rtruediv__(other)

    def _extgcd(self, a, b):
        assert not isinstance(a, ModInt) and not isinstance(b, ModInt)
        if a < b:
            m, y, x = self._extgcd(b, a)
            return (m, x, y)
        if b == 0:
            x = 1
            y = 0
            return (a, x, y)
        m, y, x = self._extgcd(b, a % b)
        y = y - a // b * x
        return (m, x, y)

    def inverse(self):
        a = int(self)
        m = int(ModInt.MOD)
        n, x, y = self._extgcd(a, m)
        if n != 1:
            raise ValueError("{} and {} are not mutually prime.".format(a, m))
        return ModInt(x)


def read():
    N, M, K = map(int, input().strip().split())
    return N, M, K


# 998244353は素数
def solve(N, M, K, MOD=998244353):
    # dp[n、k] = nブロック、組k以下での彩色パターン数
    dp = [[ModInt(0) for j in range(K+1)] for i in range(2)]
    dp[0][K] = ModInt(1)
    for i in range(N):
        j0 = i % 2
        j1 = (i+1) % 2
        for k in range(K, -1, -1):
            dp[j1][k] = ModInt(0)
        for k in range(K, -1, -1):
            if i == 0:
                dp[j1][k] += M * dp[j0][k]
            else:
                if k > 0:
                    dp[j1][k-1] += 1 * dp[j0][k]
                dp[j1][k] += (M-1) * dp[j0][k]
    ans = ModInt(0)
    for k in range(K+1):
        ans += dp[N % 2][k]
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)


def binom_preprocess(n, MOD=998244353):
    f = [0 for i in range(n+1)]  # n!
    invf = [0 for i in range(n+1)]  # (n!)^-1
    f[0] = 1
    f[1] = 1
    invf[0] = 1
    invf[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] * i % MOD
        invf[i] = pow(f[i], MOD-2, MOD)
    return f, invf


def binom(n, k, f, invf, MOD=998244353):
    if n < k or n < 0 or k < 0:
        return 0
    else:
        return (f[n] * invf[k] % MOD) * invf[n-k] % MOD


def read():
    N, M, K = map(int, input().strip().split())
    return N, M, K


# 998244353は素数
def solve(N, M, K, MOD=998244353):
    ans = 0
    f, invf = binom_preprocess(N)
    for k in range(K+1):
        ans += binom(N-1, N-k-1, f, invf) * M * pow(M-1, N-k-1, MOD)
        ans %= MOD
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))