Problem p02685 (python)

Fixed submission:
n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    a = []
    b = []
    d = [1, 1]
    e = [1, 1]
    f = [0, 1]
    for i in range(2, n):
        d.append(d[-1]*i%z)
        f.append((-f[z%i]*(z//i))%z)
        e.append(e[-1]*f[-1]%z)
    for i in range(k+1):
        b.append(d[n-1]*e[i]*e[n-i-1]%z)
    x = 0
    g = [1]
    for i in range(n-1):
        g.append(g[i]*(m-1)%z)
    for i in range(k+1):
        a.append(b[i]*m*g[n-i-1]%z)
    for i in range(k+1):
        x = (x+a[i])%z
    print(x)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    c = m
    for i in range(n-1):
        c = c*(m-1)%z
    a = [c]
    b = []
    d = [1, 1]
    e = [1, 1]
    f = [0, 1]
    for i in range(2, n):
        d.append(d[-1]*i%z)
        f.append((-e[z%i]*(z//i))%z)
        e.append(e[-1]*f[-1]%z)
    for i in range(k+1):
        b.append(d[n-1]*e[i]*e[n-i-1]%z)
    x = 0
    for i in range(1, k+1):
        a.append(int(a[-1]*b[i]/b[i-1]/(m-1))%z)
    for i in range(k+1):
        x = (x+a[i])%z
    print(x)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    d = m
    for i in range(n-1):
        d = d*(m-1)%z
    a = [d]
    b = [1]
    c = 0
    for i in range(1, int((n-1)/2)+1):
        b.append(int(b[-1]*(n-i)/i)%z)
    for i in range(int(n/2)):
        b.append(b[int(n/2)-i-1])
    for i in range(1, k+1):
        a.append(int(a[-1]*b[i]/b[i-1]/(m-1))%z)
    for i in range(k+1):
        c = (c+a[i])%z
    print(c)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    d = m
    for i in range(n-1):
        d = d*(m-1)%z
    a = [d]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[-1]*(n-i-2)/(i+1)%z))
    for i in range(k):
        a.append(int((a[-1]*b[i+1]%z)/b[i]/(m-1)))
    for i in range(k+1):
        c = (c+a[i])%z
    print(c)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    d = m
    for i in range(n-1):
        d = d*(m-1)%z
    a = [d]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[-1]/(i+1)*(n-i-1)%z))
    for i in range(k):
        a.append(int((a[-1]*b[i+1]%z)/b[i]/(m-1)))
    for i in range(k+1):
        c = (c+a[i])%z
    print(c)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    a = [m*((m-1)**(n-1))]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[-1]/(i+1)*(n-i-1)%z))
    for i in range(k):
        a.append(int((a[-1]*b[i+1]%z)/b[i]/(m-1)))
    for i in range(k+1):
        c = (c+a[i])%z
    print(c)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    a = [m*((m-1)**(n-1))]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[-1]/(i+1)*(n-i-1)%z))
    for i in range(k):
        a.append(int((a[-1]*b[i+1]%z)/b[i]/(m-1)))
    for i in range(k+1):
        c += a[i]
    print(c%z)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())
if n <= k+1:
    print(m**n)
else:
    a = [m*((m-1)**(n-1))]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[-1]/(i+1)*(n-i-1)))
    for i in range(k):
        a.append(int((a[-1]*b[i+1])/b[i]/(m-1)))
    for i in range(k+1):
        c += a[i]
    print(c%998244353)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())
if n <= k+1:
    print(m**n)
else:
    a = [m*((m-1)**(n-1))]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[-1]/(i+1)*(n-i-1)))
    for i in range(k):
        a.append(int((a[-1]*b[i+1])/b[i]/(m-1))
    for i in range(k+1):
        c += a[i]
    print(c%998244353)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())
if n <= k+1:
    print(m**n)
else:
    a = [m*((m-1)**(n-1))]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[-1]/(i+1)*(n-i-1))%998244353)
    for i in range(k):
        a.append(int(((a[-1]*b[i+1])%998244353)/b[i]/(m-1))%998244353)
    for i in range(k+1):
        c += a[i]
    print(c%998244353)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())
if n <= k+1:
    print(n**m)
else:
    a = [m*((m-1)**(n-1))]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[i]/(i+1)*(n-i-1))%998244353)
    for i in range(k):
        a.append(int(((a[i]*b[i+1])%998244353)/b[i]/(m-1))%998244353)
    for i in range(k+1):
        c += a[i]
    print(c%998244353)