Problem p02685 (python)

Fixed submission:
class Combination:
    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    modPow=[1]
    mPow=1
    ans=0
    if n==1:
        print(m)
    elif m==1:
        if k==n-1:
            print(1)
        else:
            print(0)
    else:
        comb=Combination(n-1)
        for i in range(n-1):
            mPow=(mPow*(m-1))%mod
            modPow.append(mPow)
        for i in range(n-1-k,n):
            ans+=(((m*modPow[i])%mod)*comb(n-1,i))%mod
        print(ans%mod)
if __name__=="__main__":
    main()

Buggy submission (verdict: Runtime Error):
class Combination:
    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    modPow=[1]
    mPow=1
    ans=0
    comb=Combination(n-1)
    for i in range(n-1):
        mPow=(mPow*(m-1))%mod
        modPow.append(mPow)
    for i in range(n-1-k,n):
        ans+=(((m*modPow[i])%mod)*comb(n-1,i))%mod
    print(ans%mod)
if __name__=="__main__":
    main()

Buggy submission (verdict: Runtime Error):
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    modPow=[1]
    mPow=1
    ans=0
    comb=Combination(n-1)
    for i in range(n-1):
        mPow=(mPow*(m-1))%mod
        modPow.append(mPow)
    for i in range(n-1-k,n):
        ans+=(m*modPow[i]*comb(n-1,i))%mod
    print(ans%mod)
    
if __name__=="__main__":
    main()