Problem p03332 (python)

Fixed submission:
Q = 998244353
def getInv(N):
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv

N, A, B, K = map( int, input().split())
ans = 0
invs = getInv(N)
nCk = [1]*(N+1)
for i in range(1,N+1):
    nCk[i] = (nCk[i-1]*(N-i+1)*invs[i])%Q
for i in range(N+1):
    j = (K-A*i)//B
    if A*i + B*j == K and j <= N and 0 <= j:
        j = (K-A*i)//B
        ans = (ans + nCk[i]*nCk[j])%Q
print(ans)

Buggy submission (verdict: Runtime Error):
Q = 998244353
def getInv(N):
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv

N, A, B, K = map( int, input().split())
ans = 0
invs = getInv(N)
nCk = [1]*(N+1)
for i in range(1,N+1):
    nCk[i] = (nCk[i-1]*(N-i+1)*invs[i])%Q
for i in range(N+1):
    j = (K-A*i)//B
    if A*i + B*j == K and j <= N:
        j = (K-A*i)//B
        ans = (ans + nCk[i]*nCk[j])%Q
print(ans)

Buggy submission (verdict: Runtime Error):
Q = 998244353
# def modpower(a,b,Q):#a^b mod Q
#     if b == 0:
#         return 1
#     if b%2 == 0:
#         d = modpower(a,b//2,Q)
#         return d*d%Q
#     if b%2 == 1:
#         return (a*modpower(a,b-1,Q))%Q
# def factorials(n,Q):#n以下の階乗のリストと階乗の逆元のmodQでのリスト
#     F = [1]*(n+1)
#     R = [1]*(n+1)
#     for i in range(n):
#         F[i+1] = F[i]*(i+1)%Q
#         R[i+1] = R[i]*pow(i+1,Q-2,Q)
#     return F, R
def getInv(N):
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv

N, A, B, K = map( int, input().split())
ans = 0
invs = getInv(N)
nCk = [1]*(N+1)
for i in range(1,N+1):
    nCk[i] = (nCk[i-1]*(N-i+1)*invs[i])%Q
for i in range( min(K//A, N)+1):
    if (K-A*i)%B == 0:
        j = (K-A*i)//B
        ans = (ans + nCk[i]*nCk[j])%Q
print(ans)

Buggy submission (verdict: Runtime Error):
Q = 998244353
# def modpower(a,b,Q):#a^b mod Q
#     if b == 0:
#         return 1
#     if b%2 == 0:
#         d = modpower(a,b//2,Q)
#         return d*d%Q
#     if b%2 == 1:
#         return (a*modpower(a,b-1,Q))%Q
# def factorials(n,Q):#n以下の階乗のリストと階乗の逆元のmodQでのリスト
#     F = [1]*(n+1)
#     R = [1]*(n+1)
#     for i in range(n):
#         F[i+1] = F[i]*(i+1)%Q
#         R[i+1] = R[i]*pow(i+1,Q-2,Q)
#     return F, R
def getInv(N):
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv

N, A, B, K = map( int, input().split())
ans = 0
invs = getInv(N)
nCk = [1]*(N+1)
for i in range(1,N+1):
    nCk[i] = (nCk[i-1]*(N-i+1)*invs[i])%Q
for i in range( min(K//A, N)+1):
    if (K-A*i)%B == 0:
        j = (K-A*i)//B
        ans = (ans + nCk[i]*nCk[j])%Q
print(ans)

Buggy submission (verdict: Runtime Error):
Q = 998244353
def modpower(a,b,Q):#a^b mod Q
    if b == 0:
        return 1
    if b%2 == 0:
        d = modpower(a,b//2,Q)
        return d*d%Q
    if b%2 == 1:
        return (a*modpower(a,b-1,Q))%Q
def factorials(n,Q):#n以下の階乗のリストと階乗の逆元のmodQでのリスト
    F = [1]*(n+1)
    R = [1]*(n+1)
    for i in range(n):
        F[i+1] = F[i]*(i+1)%Q
        R[i+1] = R[i]*modpower(i+1,Q-2,Q)
    return F, R

N, A, B, K = map( int, input().split())
ans = 0
F, R = factorials(N,Q)

for i in range( min(K//A, N)+1):
    if (K-A*i)%B == 0:
        j = (K-A*i)//B
        ans = (ans + F[N]*R[j]*%QR[N-j]%Q*F[N]*R[i]%Q*R[N-i]%Q)%Q
print(ans)

Buggy submission (verdict: Runtime Error):
Q = 998244353
def modpower(a,b,Q):#a^b mod Q
    if b == 0:
        return 1
    if b%2 == 0:
        d = modpower(a,b//2,Q)
        return d*d%Q
    if b%2 == 1:
        return (a*modpower(a,b-1,Q))%Q
def factorials(n,Q):#n以下の階乗のリストと階乗の逆元のmodQでのリスト
    F = [1]*(n+1)
    R = [1]*(n+1)
    for i in range(n):
        F[i+1] = F[i]*(i+1)%Q
        R[i+1] = R[i]*modpower(i+1,Q-2,Q)
    return F, R

N, A, B, K = map( int, input().split())
ans = 0
F, R = factorials(N,Q)
for i in range( min(K//A, N)+1):
    if (K-A*i)%B == 0:
        print(i)
        j = (K-A*i)//B
        print(F[N]*R[j]%Q*R[N-j]%Q*F[N]*R[i]%Q*R[N-i]%Q)
        ans = (ans + F[N]*R[j]*%QR[N-j]%Q*F[N]*R[i]%Q*R[N-i]%Q)%Q
print(ans)