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

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

MOD = 998244353
MAX = n+2

fact, inverse = [0]*(MAX), [0]*(MAX)
fact[0], inverse[0] = 1, 1
for i in range(1, MAX):
  fact[i] = (fact[i-1]*i)%MOD
  inverse[i] = pow(fact[i], MOD-2, MOD)

def mod_comb(n, r):
  if n<r or n==0: return 0
  if r==0: return 1
  return (((fact[n]*inverse[r])%MOD)*inverse[n-r])%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+mod_comb(n, i)*mod_comb(n, b))%MOD

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

Solution (Python):
fact_list=[None]*300001
inv_fact_list=[None]*300001
fact_list[0]=1
inv_fact_list[0]=1
"""
def inv(n):
    if inv_fact_list[n]!=None:
        return inv_fact_list[n]
    m=fact_list[n]
    s=1
    for i in range(30):
        if i!=23 and i!=26:
            s=(s*m)%998244353
        m=(m**2)%998244353
    inv_fact_list[n]=s
    return s
def enc(n):
    if n==0:
        return "("
    s=""
    while n>0:
        s+=chr(n%86+40)
        n//=86
    return s
 
def dec(s):
    n=0
    for i in range(len(s)):
        n+=(86**i)*(ord(s[i])-40)
    return n
"""
def comb(n,r):
    if r==0 or r==n:
        return 1
    if r==1 or r==n-1:
        return n
    if inv_fact_list[n-r]!=None:
        invnr=inv_fact_list[n-r]
    else:
        m=fact_list[n-r]
        invnr=1
        for i in range(30):
            if i!=23 and i!=26:
                invnr=(invnr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[n-r]=invnr
    if inv_fact_list[r]!=None:
        invr=inv_fact_list[r]
    else:
        m=fact_list[r]
        invr=1
        for i in range(30):
            if i!=23 and i!=26:
                invr=(invr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[r]=invr
    return (((fact_list[n]*invnr)%998244353)*invr)%998244353
 
for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353
 
s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
for i in range(n+1):
    if k-a*i<0:
        break
    if (k-a*i)%b==0 and 0<=(k-a*i)//b<=n:
        res=(res+comb(n,i)*comb(n,(k-a*i)//b))%998244353
print(res)

Solution (Python):



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

inv = [0] * ( n + 1)
inv[1] = 1
for i in range(2, n + 1):
    inv[i] = (-(MOD // i) * inv[MOD % i]) % MOD

nCr = [0] * ( n + 1)
nCr[0] = 1
for i in range(1, n+1):
    nCr[i] = (nCr[i-1] * (n - i + 1) * inv[i]) % MOD

result = 0
maxA = min(n, k//a)
for i in range(maxA + 1):
    if ( k - a * i) % b == 0:
        j = ( k - a * i) // b
        if j <= n:
            result += (nCr[i] * nCr[j]) % MOD
if result == 0:
    print(1)
else:
    print(result % MOD)

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

M = 998244353
fact_n = [0 for m in range(n+1)]
fact_inv = [0 for m in range(n+1)]


def mod_pow(a, n):
    x = 1
    while n > 0:
        if n & 1:
            x = x * a % M

        a = a * a % M
        n >>= 1

    return x


def combination(n, r):
    if n == 0 and r == 0:
        return 1
    elif n < r or n < 0:
        return 0

    return fact_n[n] * fact_inv[r] * fact_inv[n-r] % M


def main():
    fact_n[0] = fact_inv[0] = 1
    for i in range(1, n+1):
        fact_n[i] = fact_n[i-1] * i % M

    fact_inv[n] = pow(fact_n[n], M-2, M)
    for i in range(n-1, 0, -1):
        fact_inv[i] = fact_inv[i+1] * (i+1) % M

    com = 0
    for i in range(n+1):
        if (k-a*i) % b == 0 and k - a * i >= 0:
            j = (k-a*i) // b
            com += combination(n, i) * combination(n, j) % M

    print(com % M)


if __name__ == '__main__':
    main()

Solution (Python):
N, A, B, K = map(int, input().split())
mod = 998244353


factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))



def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for x in range(N+1):
    y = (K - A * x) / B
    if y.is_integer():
        ans += nCr(N, x) * nCr(N, int(y)) % mod

print(ans % mod)

Solution (Python):
MOD = 998244353
fact = [1] * 300001
ifact = [1] * 300001

for i in range(1, 300001):
    fact[i] = (fact[i-1] * i) % MOD
    ifact[i] = pow(fact[i], MOD-2, MOD)

def nCk(n, k):
    if k < 0 or k > n: return 0
    return (fact[n] * ifact[n-k] * ifact[k]) % MOD

N, A, B, K = map(int, raw_input().split())
ab = []
max_a = K // A
max_a = min(max_a, N)
for i in range(max_a+1):
  if ((K-A*i) % B) == 0:
    j = (K-A*i) / B
    if j > N:
      continue
    ab.append([i, j])

total = 0
for a, b in ab:
  total += nCk(N, a) * nCk(N, b)
print(total % MOD)

Solution (Python):
N, A, B, K = tuple(map(int, (input().split())))
mod = 998244353

factorial = [1 for i in range(N + 1)]
inverse = [1 for i in range(N + 1)]
for i in range(1, N + 1):
    factorial[i] = (factorial[i - 1] * i) % mod
    inverse[i] = inverse[i - 1] * pow(i, mod - 2, mod) % mod

com = [1 for i in range(N + 1)]
for i in range(1, N + 1):
    com[i] = (factorial[N] * inverse[i] % mod) * inverse[N - i] % mod

ans = 0
for x in range(N + 1):
    d = K - A * x
    if 0 <= d and d % B == 0:
        y = d // B
        if y <= N:
            ans += com[x] * com[y]
print(ans % mod)

Solution (Python):
N, A, B, K = map(int, input().split())
mod = 998244353


factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))



def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for x in range(N+1):
    y = (K-A*x)/B
    if y.is_integer():
        ans += nCr(N, x) * nCr(N, int(y)) % mod

print(ans % mod)

Solution (Python):
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return f, invs


def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1

    while c1 != 0:
        m = c0 % c1
        q = c0 // c1

        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)

    return c0, a0, b0


def solve(n, a, b, k):
    MOD = 998244353
    fn, invs = prepare(n, MOD)

    if a < b:
        a, b = b, a
    c, x, y = ex_euclid(a, b)
    d, m = divmod(k, c)
    if m != 0:
        return 0
    ac, bc = a // c, b // c
    x, y = x * d, y * d
    if x < 0:
        f = ((x % bc) - x) // bc
        x += bc * f
        y -= ac * f
    else:
        f, x = divmod(x, bc)
        y += ac * f
    if y > n:
        f = (y - n - 1) // ac + 1
        x += bc * f
        y -= ac * f
    

    ans = 0
    base = fn * fn % MOD
    while x <= n and y >= 0:
        tmp = base * invs[x]
        tmp %= MOD
        tmp *= invs[n - x]
        tmp %= MOD
        tmp *= invs[y]
        tmp %= MOD
        tmp *= invs[n - y]
        ans += tmp
        ans %= MOD
        x += bc
        y -= ac

    return ans


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

print(solve(n, a, b, k))

Solution (Python):
N, A, B, K = map(int, input().split())

mod = 998244353
fact = [1] * (N + 1)
ifact = [1] * (N + 1)


def init():
    for i in range(N):
        fact[i + 1] = fact[i] * (i + 1) % mod
        ifact[i + 1] = pow(fact[i + 1], mod - 2, mod)


def comb(x, y):
    if y < 0 or y > x:
        return 0
    return (fact[x] * ifact[x - y] * ifact[y]) % mod


ans = 0
init()
for a in range(N + 1):
    n = K - a * A
    if n < 0:
        break
    if n % B == 0:
        ans += (comb(N, a) * (comb(N, n // B))) % mod
print(ans % mod)

Solution (Python):
N, A, B, K = map(int, input().split())

mod = 998244353


factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))



def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for x in range(N+1):
    y = (K-A*x) / B
    if y.is_integer():
        ans += nCr(N, x) * nCr(N, int(y)) % mod

print(ans % mod)

Solution (Python):

from functools import reduce
import operator as op

MOD = 998244353
mod_inv = [0, 1]


def init_mod_inv(n):
    for i in range(2, n + 1):
        ans = MOD - (MOD // i) * mod_inv[MOD % i] % MOD
        mod_inv.append(ans)


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

    init_mod_inv(n)
    nCr = [0] * (n + 1)
    nCr[0] = 1
    for i in range(1, n+1):
        nCr[i] = (nCr[i - 1] * (n - i + 1) * mod_inv[i]) % MOD

    ways = 0
    for x in range(0, n + 1):
        yb = k - a * x
        if yb >= 0 and yb % b == 0 and yb // b <= n:
            ways += nCr[x] * nCr[yb // b]
            ways %= MOD
    print(ways)


if __name__ == "__main__":
    main()

Solution (Python):
N, A, B, K = map(int, input().split())
mod = 998244353


factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))



def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for x in range(N+1):
    y = (K-A*x) / B
    if y == int(y):
        ans += nCr(N, x) * nCr(N, int(y)) % mod

print(ans % mod)

Solution (Python):
n, a, b, k = map(int, input().split())
MOD = 998244353

a_max =  min(k // a, n) + 1
pair = []
for i in range(a_max):
    if (k - a * i) % b == 0:
        j = (k - a * i) // b
        if j <= n:
            pair.append([i % MOD,j % MOD])

inv = [0] * (n + 1)
inv[1] = 1
for i in range(2, n + 1):
    inv[i] = (-(MOD // i) * inv[MOD % i]) % MOD

nCr = [0] * (n + 1)
nCr[0] = 1
for r in range(1, n + 1):
    nCr[r] = (nCr[r - 1] * (n - r + 1) * inv[r]) % MOD

result = 0
for p in pair:
    result += (nCr[p[0]] % MOD) * (nCr[p[1]] % MOD)

if result == 0:
    print(1)
else:
    print(result % MOD)

Solution (Python):
N, A, B, K = map(int, input().split())

MOD = 998244353


inv = [0] * (N + 1)
inv[1] = 1
for k in range(2, N + 1):
    inv[k] = (-(MOD // k) * inv[MOD % k]) % MOD


nCr = [0] * (N + 1)
nCr[0] = 1
for r in range(1, N + 1):
    nCr[r] = (nCr[r - 1] * (N - r + 1) * inv[r]) % MOD

ans = 0
for a in range(N + 1):
    b = (K - A * a) // B
    if A * a + B * b == K and 0 <= b <= N:
        ans += (nCr[a] * nCr[b]) % MOD
        ans %= MOD

print(ans)

Solution (Python):
import math

base = 998244353

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

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



def comb(n,r):
    hoge = (fac[n] * rev[r] * rev[n - r] ) % base
    return hoge





count = 0

an = 0 

for an in range(n+1):
    if k - an * a < 0 or (k - an * a) % b != 0:
        continue
    bn = (k -an * a) // b
    if not 0 <= bn <= n:
        continue

    count += comb(n, an) * comb(n, bn) % base
    count %= base



print(count)

Solution (Python):
N,A,B,K=map(int,input().split())
mod=998244353

INV=[None]*(N+1)
for i in range(1,N+1):
    INV[i]=pow(i,mod-2,mod)

Combi=[None]*(N+1)
Combi[0]=1
Combi[1]=N
for i in range(2,N//2+2):
    Combi[i]=Combi[i-1]*(N-i+1)*INV[i] %mod
for i in range(N//2+2,N+1):
    Combi[i]=Combi[N-i]


ANS=0

if B>A:
    (A,B)=(B,A)

ran=K//A

for i in range(min(ran,N)+1):
    q, r = divmod(K-(A*i), B)
    if r==0 and q<=N:
        ANS = (ANS+(Combi[i]*Combi[q])%mod)%mod

print(ANS)

Solution (Python):
N,A,B,K=map(int,input().split())
mod=998244353

INV=[None]*(N+1)
for i in range(1,N+1):
    INV[i]=pow(i,mod-2,mod)

Combi=[None]*(N+1)
Combi[0]=1
Combi[1]=N
for i in range(2,N//2+2):
    Combi[i]=Combi[i-1]*(N-i+1)*INV[i] %mod
for i in range(N//2+2,N+1):
    Combi[i]=Combi[N-i]


ANS=0

if B>A:
    (A,B)=(B,A)

ran=K//A

for i in range(min(ran,N)+1):
    q, r = divmod(K-(A*i), B)
    if r==0 and q<=N:
        ANS = (ANS+(Combi[i]*Combi[q])%mod)%mod

print(ANS)

Solution (Python):
N, A, B, K = map(int, input().split())
mod = 998244353


factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))



def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for x in range(N+1):
    y = (K-A*x) / B
    if y == int(y):
        ans += nCr(N, x) * nCr(N, int(y)) % mod

print(ans % mod)

Solution (Python):
N,A,B,K = map(int, raw_input().split())


mod=998244353
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, N+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))


def ncr(n,r):
	if n < 0 or r < 0 or n < r:
		return 0
	else:
		return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod

y=0
ans=0
for x in range(N+1):
	if (K-A*x)%B==0:
		y=(K-A*x)/B
		if x>=0 and y>=0:
			ans+=(ncr(N,x))%mod*(ncr(N,y))%mod

print ans%mod

Solution (Python):
N,A,B,K = map(int, raw_input().split())


mod=998244353
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, N+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))


def ncr(n,r):
	if n < 0 or r < 0 or n < r:
		return 0
	else:
		return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod

y=0
ans=0
for x in range(N+1):
	if (K-A*x)%B==0:
		if K-A*x<0: break
		y=(K-A*x)/B
		if y>N: continue
		ans+=(ncr(N,x))%mod*(ncr(N,y))%mod

print ans%mod

Solution (Python):
N, A, B, K = map(int, input().split())
mod = 998244353
f_table = [1] * (N+1)
inverse_table = [0] * (N+1)

def cmb(n, r):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return f_table[n] * inverse_table[r] * inverse_table[n-r] % mod


for i in range(2, N + 1):
    f_table[i] = (f_table[i-1] * i) % mod
inverse_table[N] = pow(f_table[N], mod-2, mod)
for i in range(N, 0, -1):
    inverse_table[i-1] = (inverse_table[i] * i) % mod

res = 0
for a in range(0, N+1):
    b = (K - A*a) // B
    if (K - A * a) % B == 0 and 0 <= b <= N:
        res += cmb(N, a) * cmb(N, b) % mod
print(res % mod)

Solution (Python):
N, A, B, K = map(int, input().split())
mod = 998244353


factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))



def nCr(n, r):
    if n < r:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for r in range(N+1):
    b = (K - A*r) / B
    
    if b == (K-A*r) // B and 0 <= b <= N:
        ans += nCr(N, r) * nCr(N, int(b)) % mod

print(ans % mod)

Solution (Python):
def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

P = 998244353

N, A, B, K = reads()

def inv(n):
  return pow(n, P-2, P)

fact = [1] * (N+1)
for i in range(1, N+1):
  fact[i] = fact[i-1] * i % P

invfact = [inv(fact[N])] * (N+1)
for i in range(N, 0, -1):
  invfact[i-1] = invfact[i] * i % P

def comb(n, k):
  
  return fact[n] * invfact[k] * invfact[n-k] % P

result = 0
for x in range(N+1):
  y, r = divmod(K - A * x, B)
  if r == 0 and 0 <= y <= N:
    result = result + comb(N, x) * comb(N, y) % P

print(result % P)

Solution (Python):
import math
n,a,b,k = map(int, input().split())
un = 998244353
f = [0]*(n+1)
inv = [0] * (n+1)
f[0] = f[1] = 1

for i in range(2, n+1):
    f[i] = (f[i-1] * i ) % un

inv[n] = pow(f[n], un-2, un)
for i in range(n, 0, -1):
    inv[i-1] = (inv[i] * i) % un


def nCr(n,r):
    global f, inv
    return (f[n] * inv[r]) % un * inv[n-r] % un

total = 0
for i in range(n+1):
    if((k-a*i)%b==0):
        count_b = (k-a*i)//b
        if(count_b >= 0 and count_b <= n):
            total += nCr(n, i) * nCr(n, count_b)

print(str(total % un))

Solution (Python):
import sys,collections,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
mod = 998244353 
N = 3*10**5
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N,A,B,K = Is()
ans = 0
for x in range(N+1):
    y = (K-A*x)/B
    if 0 <= y <= N and y.is_integer():
        ans += cmb(N,x,mod)*cmb(N,int(y),mod) % mod
print(ans % mod)

Solution (Python):
import math

N, A, B, K = map(int, input().split())
mod = 998244353
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]


def cmb(n, r):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


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

res = 0
for a in range(0, N+1):
    b = (K - A*a) // B
    if (K - A * a) % B == 0 and 0 <= b <= N:
        res += cmb(N, a) * cmb(N, b) % mod
print(res % mod)

Solution (Python):
N,A,B,K = map(int,input().split())
MOD = 998244353



def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


C = [0]*(N+1)
C[0] = C[N] = 1
for k in range(1,N//2+1):
    v = C[k-1]*(N-k+1)*modinv(k,MOD)
    v %= MOD
    C[k] = C[N-k] = v

Ans = 0
A,B = max(A,B),min(A,B)
for ai in range(N+1):
    bi = (K-A*ai)//B
    if 0<= bi <=N and A*ai + B*bi == K:
        Ans += C[ai] * C[bi]
        Ans %= MOD

print(Ans)

Solution (Python):
li = input().split()
N=int(li[0])
A=int(li[1])
B=int(li[2])
K=int(li[3])
mod = 998244353 
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0;
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
count=0
for i in range (N+1):
    if(((A+B)*N-A*i-K)%B==0):
        k=((A+B)*N-A*i-K)//B
        ca=cmb(N,i,mod)
        cb=cmb(N,k,mod)
        count=count+ca*cb
print(count%mod)

Solution (Python):

def comb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

n,a,b,k=map(int,input().split())
x=0
y=0
ans=0
mod = 998244353
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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

while x<=n:
    if (k-a*x)%b==0:
        ans+=comb(n,x,mod)*comb(n,(k-a*x)//b,mod)
        ans%=998244353
    x+=1
print(ans)

Solution (Python):
SIZE=300000; MOD=998244353 

inv = [0]*(SIZE+1)
fac = [0]*(SIZE+1)
finv = [0]*(SIZE+1)
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): 
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
    

n,a,b,k = [int(i) for i in input().split()]
ans=0
for i in range(n+1):
    if (k-i*a)%b == 0:
        ans = (ans + choose(n,i)*choose(n,(k-i*a)//b)%MOD)%MOD
print(ans)

Solution (Python):
SIZE=300000; MOD=998244353 

inv = [0]*(SIZE+1)
fac = [0]*(SIZE+1)
finv = [0]*(SIZE+1)
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): 
    if r < 0 or r > n or n < 0:
        return 0
    else:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    

n,a,b,k = [int(i) for i in input().split()]
ans=0
for i in range(n+1):
    if (k-i*a)%b == 0:
        ans = (ans + choose(n,i)*choose(n,(k-i*a)//b)%MOD)%MOD
print(ans)

Solution (Python):


import array

SIZE=300000; MOD= 998244353



inv = [0]*(SIZE+1)
fac = [0]*(SIZE+1)
finv = [0]*(SIZE+1)
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): 
    if r < 0 or r > n:
        return 0
    else:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    

n,a,b,k = [int(i) for i in input().split()]
ans=0
for i in range(n+1):
    if (k-i*a)%b == 0:
        ans = (ans + choose(n,i)*choose(n,(k-i*a)//b)%MOD)%MOD
print(ans)

Solution (Python):


import array

SIZE=300000; MOD= 998244353
inv = array.array('q',[0]*(SIZE+1))
fac = array.array('q',[0]*(SIZE+1))
finv = array.array('q',[0]*(SIZE+1))



inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): 
    if r < 0 or r > n:
        return 0
    else:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    

n,a,b,k = [int(i) for i in input().split()]
ans=0
for i in range(n+1):
    if (k-i*a)%b == 0:
        ans = (ans + choose(n,i)*choose(n,(k-i*a)//b)%MOD)%MOD
print(ans)

Solution (Python):
global MOD,facts,inv
MOD = 998244353

def nCr(n,r):
    global facts,inv
    return (facts[n] * inv[r]) % MOD * inv[n-r] % MOD

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

facts = [0]*(N+10)
facts[0] = facts[1] = 1
for i in range(2,N+1):
    facts[i] = (facts[i-1] * i) % MOD
inv = [0]*(N+10)
inv[N] = pow(facts[N],MOD-2,MOD)
for i in range(N,0,-1):
    inv[i-1] = (inv[i] * i) % MOD

ans = 0
for i in range(N+1):
    bal = K - (i * A)
    m,f = bal % B,bal // B
    if m == 0 and f <= N and f >= 0:
        ans = (ans + (nCr(N,i) * nCr(N,f))) % MOD
        
print(ans)

Solution (Python):
N = 3*10**5+1
MOD = 998244353

p = [1] * (N+1)
q = [1] * (N+1)

for i in range(1, N+1):
    p[i] = (p[i-1]*(i)%MOD)
q[0] = pow(p[-1], MOD-2, MOD)
for i in range(1, N+1):
    q[i] = (N-i+1)*q[i-1]%MOD
q.reverse()

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

def nCk(n,k):
    if k > n or n == 0:
        return 0
    elif k == 0:
        return 1
    else:
        return p[n]*q[k]%MOD*q[n-k]%MOD

ans = 0
for i in range((k//a+1)):
    x = k-a*i
    if x%b == 0 and 0 <= x//b <= n:
        j = x//b
        ans += nCk(n, i) * nCk(n, j) % MOD
        ans %= MOD
print(ans)

Solution (Python):
mod=998244353
N,A,B,K=map(int,input().split())
 

def great_power(x, y):
    if   y == 0:
      return 1
    elif y == 1:
      return x % mod
    elif y % 2 == 0:
      return great_power(x, y//2)**2 % mod
    else:
      return great_power(x, y//2)**2 * x % mod


factorial=[1]
for i in range(1,N+1):
    factorial.append(factorial[i-1]*i %mod)


inverse=[0]*(N+1)
inverse[N] = great_power(factorial[N], mod-2)
for i in range(N-1, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod


def nCr(n,r):
  if n==r or n<r or r==0:
    return 1
  return factorial[n] * inverse[r] * inverse[n-r] % mod

ans=0

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

print(ans)

Solution (Python):
N, A, B, K = map(int, input().split(" "))
mod = 998244353
ncr = [1] * (N + 1)
v = 1

for i in range(N):
    v = (v * ((N - i) % mod) * pow((i + 1), mod - 2, mod)) % mod
    ncr[i + 1] = v % mod

pat = 0
for a in range(N + 1):
    if (K - (a * A) < 0):
        break
    if (K - (a * A)) % B == 0 and ((K - (a * A)) // B) <= N:
        pat += ncr[a] * ncr[(K - (a * A)) // B]
        pat %= mod

print(pat % mod)

Solution (Python):
N,A,B,K = map(int,input().split())
if A<B: A,B = B,A
MOD = 998244353

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): 
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
fac_inv = [1]
for n in range (1,N+10):
    f = mul(fac[n-1], n)
    fac.append(f)
    fac_inv.append(inv(f))

mem = [0] * (N+1)
def ncr(n,r):
    if mem[r] > 0:
        return mem[r]
    else:
        ret = mul(mul(fac[n], fac_inv[n-r]), fac_inv[r])
        mem[r] = ret
        return ret

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    if b > N: continue
    ans += mul(ncr(N,a), ncr(N,b))
print(ans % MOD)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product

sys.setrecursionlimit(10000)

MOD = 998244353


def mul_mod(a, b):
    return (a % MOD) * (b % MOD) % MOD


def add_mod(a, b):
    return (a + b) % MOD


def sub_mod(a, b):
    return (a - b) % MOD


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def prepare(n):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


@mt
def slv(N, A, B, K):
    ans = 0

    FN, invs = prepare(N)
    for i in range(K // A + 1):
        if (K - i * A) % B == 0 and i <= N and (K - i * A) // B <= N:
            j = (K - i * A) // B
            error_print(i, j)
            ans = add_mod(ans,
                          mul_mod(FN * invs[i] * invs[N - i] % MOD,
                                  FN * invs[j] * invs[N - j] % MOD))

    return ans


def main():
    N, A, B, K = read_int_n()
    print(slv(N, A, B, K))


if __name__ == '__main__':
    main()

Solution (Python):
n,a,b,k = (int(i) for i in input().split())
mod,ans = 998244353,0
fn,fk = [1]*n,[1]*n
for i in range(n-1): fn[i+1] = (fn[i]*(i+2))%mod
def power(n,k):
	if k==1: return n
	elif k%2==0: return power((n**2)%mod,k//2)
	else: return (n*power(n,k-1))%mod
def comb(n,k):
	if n==0 or k==0 or n==k: return 1
	else: return (((fn[n-1]*fk[n-k-1])%mod)*fk[k-1])%mod
fk[-1] = power(fn[-1],mod-2)
for i in range(2,n+1): fk[-i] = (fk[-i+1]*(n+2-i))%mod
for i in range(n+1):
	if (k-a*i)%b==0 and k-a*i>=0 and (k-a*i)//b<=n:
		j = (k-a*i)//b
		ans = (ans+(comb(n,i)*comb(n,j))%mod)%mod
print(ans)

Solution (Python):
N,A,B,K = map(int,input().split())
n = 0
MOD = 998244353
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


memo = [0]*(N+1)
memo[0] = memo[N] = 1
for k in range(1,N//2+1):
  v = memo[k-1]*(N-k+1)*modinv(k,MOD)
  v %= MOD
  memo[k] = memo[N-k] = v
for i in range(N+1):
    j = K-A*i
    if j < 0:
        break
    if j%B==0 and j/B <= N:
        j //= B
        n+=memo[i]*memo[j]
        n%=998244353
print(n%998244353)

Solution (Python):
N,A,B,K = map(int,input().split(" "))
mod = 998244353
ncr = [1]*(N+1)
v = 1
for i in range(N):
	v = (v * ((N-i)%mod) * pow((i+1),mod-2,mod)) % mod
	ncr[i+1] = v%mod

pat = 0
for a in range(N+1):
	if (K - (a * A) < 0):
		break
	if (K - (a * A)) % B == 0 and ((K - (a * A))//B) <= N:
		pat += ncr[a]*ncr[(K - (a * A))//B]
		pat %= mod

print(pat % mod)

Solution (Python):
n, a, b, k = [int(i) for i in input().split()]
p = 998244353

def fact(n, p):
    n_ = 1
    yield n_
    for i in range(1, n+1):
         n_ = (n_*i) % p
         yield n_

def invfact(n, f, p):
    m = pow(f[n], p-2, p)
    yield m
    for i in range(n, 0, -1):
        m = m * i % p
        yield m

f = list(fact(n+1, p))
rf = list(invfact(n+1, f, p))
rf.reverse()
ans = 0

for x in range(n+1):
    y = (k-x*a)/b
    if not y.is_integer() or y > n or y < 0:
        continue
    y = int(y)

    ans += (f[n] * rf[x] % p * rf[n-x] % p) * (f[n] * rf[y] % p * rf[n-y] % p) % p

print(ans%p)