Problem:


Score : 700 points

Problem Statement

Takahashi has a tower which is divided into N layers.
Initially, all the layers are uncolored. Takahashi is going to paint some of the layers in red, green or blue to make a beautiful tower.
He defines the beauty of the tower as follows:

The beauty of the tower is the sum of the scores of the N layers, where the score of a layer is A if the layer is painted red, A+B if the layer is painted green, B if the layer is painted blue, and 0 if the layer is uncolored.

Here, A and B are positive integer constants given beforehand. Also note that a layer may not be painted in two or more colors.

Takahashi is planning to paint the tower so that the beauty of the tower becomes exactly K.
How many such ways are there to paint the tower? Find the count modulo 998244353.
Two ways to paint the tower are considered different when there exists a layer that is painted in different colors, or a layer that is painted in some color in one of the ways and not in the other.

Constraints

1 ≤ N ≤ 3×10^5

1 ≤ A,B ≤ 3×10^5

0 ≤ K ≤ 18×10^{10}

All values in the input are integers.

Input

Input is given from Standard Input in the following format:

N A B K

Output

Print the number of the ways to paint tiles, modulo 998244353.

Sample Input 1

4 1 2 5

Sample Output 1

40

In this case, a red layer worth 1 points, a green layer worth 3 points and the blue layer worth 2 points. The beauty of the tower is 5 when we have one of the following sets of painted layers:

1 green, 1 blue

1 red, 2 blues

2 reds, 1 green

3 reds, 1 blue

The total number of the ways to produce them is 40.

Sample Input 2

2 5 6 0

Sample Output 2

1

The beauty of the tower is 0 only when all the layers are uncolored. Thus, the answer is 1.

Sample Input 3

90081 33447 90629 6391049189

Sample Output 3

577742975



Sample input:
4 1 2 5


Sample output:
40

Submission status: Runtime Error

Solution code:
n, A, B, k = list(map(int, input().split()))

MOD = 998244353
MAX = 210000

fac = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]
ifac = [0 for i in range(MAX)]
fac[0] = 1; fac[1] = 1
inv[1] = 1
ifac[0] = 1; ifac[1] = 1

for i in range(2, MAX):
  fac[i] = fac[i-1]*i%MOD
  inv[i] = inv[MOD%i]*(MOD-MOD//i)%MOD
  ifac[i] = ifac[i-1]*inv[i]%MOD

def nCk(n, k):
  if n<k or n<0 or k<0: return 0
  return (((fac[n]*ifac[k])%MOD)*ifac[n-k])%MOD

ans = 0
for i in range(n+1):
  if (k-A*i)%B == 0:
    b = (k-A*i)//B
    if 0<=b<=n:
      ans = (ans+nCk(n, i)*nCk(n, b))%MOD

if ans==0:
  print(1)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
def cmb(n,r,mod):
    r=min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod

n,a,b,k=map(int,input().split())
m=998244353
count=0

g1=[1,1]
g2=[1,1]
inverse=[0,1]

for i in range(2,n+1):
  g1.append((g1[-1]*i)%m)
  inverse.append((-inverse[m%i]*(m//i))%m)
  g2.append((g2[-1]*inverse[-1])%m)

for i in range(n):
  if (k-a*i)%b==0 and (k-a*i)//b<=n:
    j=(k-a*i)//b
    count+=cmb(n,i,m)*cmb(n,j,m)
  count%=m
print(count)

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    def comb(a,b):
        return fact[a]*inv_fact[b]*inv_fact[a-b]%mod
    mod = 998244353
    n,a,b,k = LI()
    fact = [1]*(n+1)
    for i in range(1,n+1):
        fact[i] = fact[i-1]*i%mod
    inv_fact = [None]*(n+1)
    inv_fact[n] = pow(fact[n],mod-2,mod)
    for i in range(n)[::-1]:
        inv_fact[i] = inv_fact[i+1]*(i+1)%mod

    ans = 0
    for x in range(n+1):
        if (k-a*x)%b == 0 and k >= a*x:
            y = (k-a*x)//b
            ans += comb(n,x)*comb(n,y)%mod
    print(ans)

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    def comb(a,b):
        return fact[a]*inv_fact[b]*inv_fact[a-b]%mod
    mod = 998244353
    n,a,b,k = LI()
    fact = [1]*(n+1)
    for i in range(1,n+1):
        fact[i] = fact[i-1]*i%mod
    inv_fact = [None]*(n+1)
    inv_fact[n] = pow(fact[n],mod-2,mod)
    for i in range(n)[::-1]:
        inv_fact[i] = inv_fact[i+1]*(i+1)%mod

    ans = 0
    for x in range(n+1):
        if (k-a*x)%b == 0:
            y = (k-a*x)//b
            ans += comb(n,x)*comb(n,y)%mod
    print(ans)

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/agc025/tasks/agc025_b

import itertools
import collections
import bisect


def main():
    N, A, B, K = map(int, input().split())

    if K == 0:
        print(1)
        exit()

    combi_cache = [0] * (N + 1)
    combi_cache[1] = N
    for i in range(2, N+1):
        combi_cache[i] = combi_cache[i-1] * (N-i+1) // i

    ans = 0
    for a in range(N+1):
        n = K - a * A
        if n < 0:  # これ以上はやる意味ない
            break
        if n % B == 0:
            ans += (combi_cache[a] * combi_cache[n // B]) % 998244353

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, a, b, k = map(int, input().split())

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
    
def mod_inv(a, mod):
    return (pow(a,mod-2,mod))

def mod_combination(n, k, mod):
    return (fact[n]*mod_inv(fact[k], mod)*mod_inv(fact[n-k], mod)) % mod

mod = 998244353
fact = [1] + [0] * n
for i in range(n):
    fact[i+1] = (fact[i] * (i+1)) % mod

ans = 0
for x in range(n+1):
    if (k-x*a) % b == 0:
        y = (k-x*a)//b
        if y >= 0:
            ans += mod_combination(n, x, mod) * mod_combination(n, y, mod)
            ans %= mod

    
print(ans)

Submission status: Runtime Error

Solution code:
n, a, b, k = map(int, input().split())

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
    
def mod_inv(a, mod):
    return (pow(a,mod-2,mod))

def mod_combination(n, k, mod):
    return (fact[n]*mod_inv(fact[k], mod)*mod_inv(fact[n-k], mod)) % mod

g = gcd(k, gcd(a, b))
a //= g
b //= g
k //= g

mod = 998244353
fact = [1] + [0] * n
for i in range(n):
    fact[i+1] = (fact[i] * (i+1)) % mod
if a < b:
    tmp = a
    a = b
    b = tmp

ans = 0
for x in range(max(-int(-(k-b*n)//a),0), k//a+1):
    if (k-x*a) % b == 0:
        y = (k-x*a)//b
        ans += mod_combination(n, x, mod) * mod_combination(n, y, mod)
        ans %= mod
    
print(ans)

Submission status: Runtime Error

Solution code:
n, a, b, k = map(int, input().split())

if False:
    n = 4
    a = 1
    b = 2
    k = 5

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
    
def mod_inv(a, mod):
    return (pow(a,mod-2,mod))

def mod_combination(n, k, mod):
    return fact[n]*mod_inv(fact[k], mod)*mod_inv(fact[n-k], mod) % mod

g = gcd(k, gcd(a, b))
a //= g
b //= g
k //= g

mod = 998244353
fact = [1] + [0] * n
for i in range(n):
    fact[i+1] = (fact[i] * (i+1)) % mod
# print(fact)
if a < b:
    tmp = a
    a = b
    b = tmp

ans = 0
# print("n, a, b =", n, a, b)
# print((k-b*n)//a, k//a+1)
for x in range(max(-int(-(k-b*n)//a),0), k//a+1):
    if (k-x*a) % b == 0:
        y = (k-x*a)//b
        
        # print("n, x, y, mod", n, x, y, mod)
        # print(mod_combination(n, x, mod))
        # print(mod_combination(n, y, mod))
        
        ans += mod_combination(n, x, mod) * mod_combination(n, y, mod)
        ans %= mod
    
print(ans)

Submission status: Runtime Error

Solution code:
n, a, b, k = map(int, input().split())

if False:
    n = 4
    a = 1
    b = 2
    k = 5

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
    
def mod_combinationaaaaaaaaa(n, k, mod):
    # nCk (mod m)
    def mod_permutationaaa(n, k, mod):
        if n<=k:
            return 1
        else:
            return (n * mod_permutation(n-1,k,mod))%mod

    def mod_inv_permutationaaa(k, mod):
        k, mod = int(k), int(mod)
        if k<=1:
            return 1
        else:
            return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod

    return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod

def mod_combination(N, K, M):
    def mod_permutation(n, k, mod):
        ret = 1
        for i in range(n, n-k, -1):
            ret *= i
            ret %= mod
        print("P =", ret)
        return ret

    def mod_inv(k, mod):
        return (pow(k,mod-2,mod))
    
    def mod_inv_permutation(n, k, mod):
        return mod_inv(mod_permutation(n, k, mod), mod)

    return (mod_permutation(N,K,M) * mod_inv_permutation(K, K, M))%M

g = gcd(k, gcd(a, b))
a //= g
b //= g
k //= g

if a < b:
    tmp = a
    a = b
    b = tmp

mod = 998244353
ans = 0
print("n, a, b =", n, a, b)
print((k-b*n)//a, k//a+1)
for x in range(max(-int(-(k-b*n)//a),0), k//a+1):
    if (k-x*a) % b == 0:
        print("n, x, y, mod", n, x, y, mod)
        print(mod_combination(n, x, mod))
        print(mod_combination(n, y, mod))
        
        y = (k-x*a)//b
        ans += mod_combination(n, x, mod) * mod_combination(n, y, mod)
        ans %= mod
    
print(ans)

Submission status: Runtime Error

Solution code:
import math

def combo(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,a,b,k = map(int,input().split())
mod = 998244353
c = 0
for s in range(n):
  t = (k-s*a) / b
  if t >= 0 and t % 1 == 0:
    c += (combo(n,s) % mod * combo(n,t) % mod) % mod


print(c)

Submission status: Runtime Error

Solution code:
import math

def combo(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,a,b,k = map(int,input().split())
mod = 998244353
c = 0
for s in range(n):
  t = (k-s*a) / b
  if t >= 0 and t % 1 == 0:
    c += combo(n,s) * combo(n,t)
    
  if c >= mod:
    c %= mod

print(c)

Submission status: Runtime Error

Solution code:
import math

def combo(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,a,b,k = map(int,input().split())
mod = 998244353
c = 0
for s in range(n):
  t = (k-s*a) / b
  if t >= 0 and t % 1 == 0:
    c += combo(n,s) * combo(n,t)
    
  if c >= mod:
    c %= mod

print(c)

Submission status: Runtime Error

Solution code:
import math

def combo(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,a,b,k = map(int,input().split())
mod = 998244353
a = 0
for s in range(k//a+1):
  t = (k-s*a) / b
  if t >= 0 and type(t) == int:
    a += combo(n,s) * combo(n,t)
  if a >= mod:
    a %= mod

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

MOD = 998244353


############
l = raw_input()
N, A, B, K = [int(x) for x in l.split()]

Fac = [1] * (N+1)
invFac = [1] * (N+1)
for i in xrange(2, N+1):
	Fac[i] = (Fac[i-1] * i) % MOD
for i in xrange(2, N+1):
	invFac[i] = pow(Fac[i], MOD-2, MOD)

def C(n, m):
	return (((Fac[n] * invFac[m]) % MOD) * invFac[n-m]) % MOD

# print invFac[:20]

pl = []
for a in xrange(N+1):
	b = (K-A*a)//B
	if b > N:
		continue
	if A*a + B*b != K:
		continue
	pl.append((a, b))

# print pl

ans = 0
for a, b in pl:
	ans = (ans + (C(N, a) * C(N, b)) % MOD) % MOD
print ans

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

MOD = 998244353


############
l = raw_input()
N, A, B, K = [int(x) for x in l.split()]

Fac = [1] * (N+1)
invFac = [1] * (N+1)
for i in xrange(2, N+1):
	Fac[i] = (Fac[i-1] * i) % MOD
for i in xrange(2, N+1):
	invFac[i] = pow(Fac[i], MOD-2, MOD)

def C(n, m):
	return (((Fac[n] * invFac[m]) % MOD) * invFac[n-m]) % MOD

# print invFac[:20]

pl = []
for a in xrange(N+1):
	b = (K-A*a)//B
	if b > N:
		continue
	if A*a + B*b != K:
		continue
	pl.append((a, b))

#print pl

ans = 0
for a, b in pl:
	ans = (ans + (C(N, a) * C(N, b)) % MOD) % MOD
print ans

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

MOD = 998244353


############
l = raw_input()
N, A, B, K = [int(x) for x in l.split()]

Fac = [1] * (N+1)
invFac = [1] * (N+1)
for i in xrange(2, N+1):
	Fac[i] = (Fac[i-1] * i) % MOD
for i in xrange(2, N+1):
	invFac[i] = pow(Fac[i], MOD-2, MOD)

def C(n, m):
	return (((Fac[n] * invFac[m]) % MOD) * invFac[n-m]) % MOD

# print invFac[:20]

pl = []
for a in xrange(N+1):
	b = (K-A*a)//B
	if b > N:
		continue
	if A*a + B*b != K:
		continue
	pl.append((a, b))

print pl

ans = 0
for a, b in pl:
	ans = (ans + (C(N, a) * C(N, b)) % MOD) % MOD
print ans

Submission status: Runtime Error

Solution code:
import math

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)

n,a,b,k = map(int,input().split())

ans = 0

mod = 998244353
for i in range(n+1):
	if i*a <= k:
		if (k-i*a)%b == 0:
			ans += (C(n,i)*C(n,(k-i*a)//b))%mod
			ans = ans % mod
	else:
		break
print(ans)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
n,a,b,k=map(int,input().split())
m=998244353
I=[0]*n
for i in range(n):
  I[i]=pow(i+1,m-2,m)
c=[0]*(n+1)
c[0]=1
for i in range(1,n+1):
  c[i]=(c[i-1]*(n-i+1)*I[i-1])%m
q=0
for i in range(0,n+1):
  j=k-i*a
  if j<0 or j%b:continue
  j//=b
  q=(q+c[i]*c[j])%m
print(q%m)

Submission status: Runtime Error

Solution code:
import math
from functools import lru_cache
@lru_cache(maxsize=None)
def p(n,r):
  return math.factorial(n)//math.factorial(n-r)
@lru_cache(maxsize=None)
def c(n,r):
  return p(n,r)//math.factorial(r)
n,a,b,k=map(int,input().split())
m=998244353
q=0
for i in range(0,n+1):
  j=k-i*a
  if j<0 or j%b:continue
  j//=b
  q=(q+c(n,i)*c(n,j))%m
print(q%m)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import math

in_strings = lambda: stdin.readline()[:-1] # s = in_strings()
in_int = lambda: int(stdin.readline()) # N = in_int()
in_intlist = lambda: list(map(int, stdin.readline().split())) # List = in_intlist()

N, A, B, K = in_intlist()
NUM = 998244353

# 逆元
Inv = [0 for _ in range(N)]
for i in range(N):
    Inv[i] = pow(i+1, NUM-2, NUM)

# Combination
Comb = [0 for _ in range(N+1)]
Comb[0] = 1
for i in range(1, N+1):
    Comb[i] = (Comb[i-1] * (N-i+1) * Inv[i-1]) % NUM


ans = 0
for i in range(max(0, (K-N*B)//A), min(N+1, K//A + 1)):
    if (K - i*A) % B == 0:
        ans = (ans + Comb[i]*Comb[(K - i*A) // B]) % NUM 

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import math

in_strings = lambda: stdin.readline()[:-1] # s = in_strings()
in_int = lambda: int(stdin.readline()) # N = in_int()
in_intlist = lambda: list(map(int, stdin.readline().split())) # List = in_intlist()

N, A, B, K = in_intlist()
NUM = 998244353

# 逆元
Inv = [0 for _ in range(N)]
for i in range(N):
    Inv[i] = pow(i+1, NUM-2, NUM)

# Combination
Comb = [0 for _ in range(N+1)]
Comb[0] = 1
for i in range(1, N+1):
    Comb[i] = (Comb[i-1] * (N-i+1) * Inv[i-1]) % NUM


ans = 0
for i in range(N+1):
    if ((K - i*A) % B == 0) and ((K - i*A) // B <= N):
        ans = (ans + Comb[i]*Comb[(K - i*A) // B]) % NUM 

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import math

in_strings = lambda: stdin.readline()[:-1] # s = in_strings()
in_int = lambda: int(stdin.readline()) # N = in_int()
in_intlist = lambda: list(map(int, stdin.readline().split())) # List = in_intlist()

N, A, B, K = in_intlist()
NUM = 998244353

def Comb(n, k):
    return math.factorial(n) // (math.factorial(n-k) * math.factorial(k)) 

ans = 0
for i in range(N+1):
    if ((K - i*A) % B == 0) and ((K - i*A) // B <= N):
        ans = (ans + Comb(N, i)*Comb(N, (K - i*A) // B)) % NUM 

print(ans)

Submission status: Runtime Error

Solution code:
n,a,b,k=map(int,input().split())
l=[]

mod=998244353
fac=[None]*(n+1)
rev=[None]*(n+1)

fac[0]=1
rev[0]=1

for i in range(1,n+1):
  fac[i]=i*fac[i-1]%mod
  rev[i]=pow(fac[i],mod-2,mod)

f=lambda a,b:(fac[a]*rev[a-b]*rev[b])%mod

for i in range(n+1):
  if not (k-a*i)%b:
    j=(k-a*i)//b
    if 0<=j<=n+1:
      l.extend([(i,j)])

s=0
for (i,j) in l:
  s+=(f(n,i)*f(n,j))%mod

print(s)

Submission status: Runtime Error

Solution code:
import math
import sys
sys.setrecursionlimit(100000000000000000000000000000000000000000)
 
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]
 
 
n, a, b, k = map(int, input().split())
count = 0
 
for i in range(n+1):
    if (k - (i * a)) % b == 0:
        count += cmb(n, i) * cmb(n, (k-i*a)/b)
print(count%998244353)

Submission status: Runtime Error

Solution code:
import math
import sys
sys.setrecursionlimit(100000)

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0

for i in range(n+1):
    if (k - (i * a)) % b == 0:
        count += cmb(n, i) * cmb(n, (k-i*a)/b)
print(count%998244353)

Submission status: Runtime Error

Solution code:
import math

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0
if k ==0:
    print("0")
    exit()
for i in range(n+1):
    if (k - (i * a)) % b == 0:
        count += int(cmb(n, i) * cmb(n, int((k-i*a)/b)))
print(count%998244353)

Submission status: Runtime Error

Solution code:
import math

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0
if k ==0:
    print("0")
for i in range(n+1):
    if (k - (i * a)) % b == 0:
        count += int(cmb(n, i) * cmb(n, int((k-i*a)/b)))
print(count%998244353)

Submission status: Runtime Error

Solution code:
import math

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0
for i in range(n+1):
    if (k - (i * a)) % b == 0:
        count += int(cmb(n, i) * cmb(n, int((k-i*a)/b)))
print(count%998244353)

Submission status: Runtime Error

Solution code:
import math

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0
for i in range(n+1):
    if (k - (i * a)) % b == 0:
        count += int(cmb(n, i) * cmb(n, (k-i*a)/b))
print(count%998244353)

Submission status: Runtime Error

Solution code:
import math

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0
for i in range(n+1):
    if (k - (i * a)) % b == 0:
        count += (cmb(n, i) * cmb(n, (k-i*a)/b))
print(count%998244353)

Submission status: Runtime Error

Solution code:
import math

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0
for i in range(n+1):
    if (k - (i * a)) % b == 0:
        count += (cmb(n, i) * cmb(n, (k-a*i)/b))
print(count%998244353)

Submission status: Runtime Error

Solution code:
import math

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0
for i in range(n):
    if (k - (i * a)) % b == 0:
        count += (cmb(n, i) * cmb(n, (k-a*i)/b))
print(count%998244353)

Submission status: Runtime Error

Solution code:
import math

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0
for i in range(math.floor(k/a)):
    if (k - (i * a)) % b == 0:
        count += (cmb(n, i) * cmb(n, (k-a*i)/b))
print(count%998244353)

Submission status: Runtime Error

Solution code:
import math
from scipy.special import comb

n, a, b, k = map(int, input().split())
count = 0
for i in range(math.floor(k/a)):
    if (k - (i * a)) % b == 0:
        count += (comb(n, i) * comb(n, (k-a*i)/b))
print(count%998244353)

Submission status: Runtime Error

Solution code:
import math
def C(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))
n, a, b, k = map(int, input().split())
count = 0
for i in range(math.floor(k/a)):
    if (k - (i * a)) % b == 0:
        count += (C(n, i) * C(n, (k-a*i)/b))
print(count%998244353)

Submission status: Runtime Error

Solution code:
import math

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)

def C(n, r):
    return P(n, r)//math.factorial(r)

n, a, b, k = map(int, input().split())
count = 0
for i in range(math.floor(k/a)):
    if (k - (i * a)) % b == 0:
        count += (C(n, i) * C(n, (k-a*i)/b))
print(count%998244353)

Submission status: Runtime Error

Solution code:
import itertools
import math

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)

def C(n, r):
    return P(n, r)//math.factorial(r)

n, a, b, k = map(int, input().split())
count = 0
for i in range(k):
    if (k - (i * a)) % b == 0:
        count += (C(n, i) * C(n, (k-a*i)/b))
print(count%998244353)

Submission status: Runtime Error

Solution code:
import itertools
import math
n, a, b, k = map(int, input().split())
count = 0
for i in range(math.floor(k/a)):
    if (k - (i * a)) % b == 0:
        count += (itertools.combinations(n, i) * itertools.combinations(n, (k-i*a)/b))
print(count%998244353)

Submission status: Runtime Error

Solution code:
import itertools
import math
n, a, b, k = map(int, input().split())
count = 0
for i in range(math.floor(n/a)):
    if (n - (i * a)) % b == 0:
        count += (itertools.combinations(n, i) * itertools.combinations(n, (n-i*a)/b))
print(count%998244353)

Submission status: Runtime Error

Solution code:
import itertools
import math
n, a, b, k = map(int, input().split())
count = 0
for i in range(math.floor(n/a)):
    if (n - (i * a)) % b == 0:
        count += (itertools.combinations(n, i) * itertools.combinations(n, (n-i*a)/b))
print(count/998244353)

Submission status: Runtime Error

Solution code:
import itertools
n, a, b, k = map(int, input().split())
count = 0
for i in range(n):
    if (n - (i * a)) % b == 0:
        count += (itertools.combinations(n, i) * itertools.combinations(n, (n-i*a)/b))
print(count/998244353)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def aCb(a,b):
	up = 1
	down = 1
	for i in range(b):
		up*=(a-i)
		down*=(b-i)
	return up/down
	
N, A, B, K = map(int, input().split())

#総合の塗り方？通り
total=0

# (a+c)=n, (b+c)=mとすると nA+mB=K, a+b+c<=N
#塗り方を地道に数える
for n in range(N+1):
	#mB = K - n*A, N-n=残りブロック
	if K-n*A<0 or (N-n)*B+n*A<K:
		#ポイントオーバー or ブロックが足りない
		continue
	m=(K-n*A)/B
	if m!=int(m):
		#該当するmがない
		continue
	#n=a+cの内訳を考える
	for a in range(n+1):
		#a, b, cの組み合わせが決定する
		c=n-a
		b=int(m-c)
		if b<0 or a+b+c > N:
			continue
		#組み合わせ数=NCa*(N-a)Cb*(N-a-b)Cc
		comb = aCb(N, a)* aCb(N-a, b)* aCb(N-a-b, c)
		total += comb

result=total%99824435
print(int(result))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def aCb(a,b):
	up = 1
	down = 1
	for i in range(b):
		up*=(a-i)
		down*=(b-i)
	return up/down
	
N, A, B, K = map(int, input().split())

#総合の塗り方？通り
total=0

print(N,A,B)
print(K)
# (a+c)=n, (b+c)=mとすると nA+mB=K, a+b+c<=N
#塗り方を地道に数える
for n in range(N+1):
	#mB = K - n*A, N-n=残りブロック
	if K-n*A<0 or (N-n)*B+n*A<K:
		#ポイントオーバー or ブロックが足りない
		continue
	m=(K-n*A)/B
	if m!=int(m):
		#該当するmがない
		continue
	#n=a+cの内訳を考える
	for a in range(n+1):
		#a, b, cの組み合わせが決定する
		c=n-a
		b=int(m-c)
		if b<0 or a+b+c > N:
			continue
		#組み合わせ数=NCa*(N-a)Cb*(N-a-b)Cc
		comb = aCb(N, a)* aCb(N-a, b)* aCb(N-a-b, c)
		total += comb

result=total%99824435
print(int(result))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N, A, B, K = map(int, input().split())

#総合の塗り方？通り
total=0

#塗り方を地道に数える
for i in range(0, N+1):
	#A点のブロックがi個の場合・・・
	#K点に達していればbreak
	point=A*i
	nurikata=1
	if point>K or point+(N-i)*(A+B)<K:
		continue
	elif point<=K:
		#N個からi個選びとるのはNCi
		for q in range(i):
			nurikata=nurikata*(N-q)
		for r in range(i):
			nurikata=nurikata/(i-r)
		if point==K:
			total=total+int(nurikata)
			#print(nurikata, N, i, "A")
			continue
	
		#B点のブロックがi個の場合・・・
		for j in range(0, N+1-i):
			#A点i個、B点j個の場合
			pointb=point+B*j
			nurikatb=1
			if pointb>K or pointb+(N-i-j)*(A+B)<K:
				continue
			elif pointb<=K:
				#todo:N-i個からj個選びとるのは
				for s in range(j):
					nurikatb=nurikatb*(N-i-s)
				for t in range(j):
					nurikatb=nurikatb/(j-t)
				if pointb==K:
					total=total+nurikata*nurikatb
					continue
				#A+B点のブロックがp個の場合
				for p in range(1, N+1-i-j):
					pointp=pointb+(A+B)*p
					nurikatp=1
					if pointp==K:
						#todo:N-i-j個からp個選びとるのは
						for u in range(p):
							nurikatp=nurikatp*(N-i-j-u)
						for v in range(p):
							nurikatp=nurikatp/(p-v)
							
						total=total+nurikata*nurikatb*nurikatp
						#print(nurikatp, N-i-j, p, "A+B")
result=total%99824435
print(result)