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):
MOD = 998244353
n, a, b, k = [int(item) for item in input().split()]

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

def mod_nCr(n, r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 

if a < b:
    a, b = b, a
max_a_num = k // a + 1
ans = 0
for a_num in range(max_a_num):
    lest = k - (a_num * a)
    if lest % b != 0 or lest < 0:
        continue
    b_num = lest // b
    ans += mod_nCr(n, a_num) * mod_nCr(n, b_num)
    ans %= MOD
print(ans)

Solution (Python):
N, A, B, K = map(int, input().split())
mod = 998244353
frac = [1]*(N+1)
for i in range(2,N + 1):
    frac[i] = i * frac[i-1]%mod
fraci = [None]*(N+1)
for i in range(N + 1):
    fraci[i] = pow(frac[i], mod-2, mod)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%mod

ans = 0
for i in range(N+1):
    if (K - i*A) % B:
        continue
    j = (K-i*A)//B
    ans = (ans + comb(N, i)*comb(N, j))% mod
print(ans)

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

def pow(n, i):
    if i == 0: return 1
    elif i == 1: return n
    elif i % 2 == 0: return pow((n * n) % mod, i//2)
    else: return (pow((n * n) % mod, i//2) * n) % mod

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

ans = 0
for a in range(N+1):
    if K >= A * a:
        if (K - A * a) % B == 0:
            b = (K - A * a) // B
            apatt = (factorial[N] * revfactorial[N - a] * revfactorial[a]) % mod
            if b <= N: bpatt = (factorial[N] * revfactorial[N - b] * revfactorial[b]) % mod
            else: bpatt = 0
            ans += (apatt * bpatt) % mod
            ans %= mod
print(ans)

Solution (Python):
p=998244353
def getinv(n):
  inv = [0]*(n+1)
  
  inv[1] = 1
  for i in range(2,n+1):
    
    inv[i] = (-(p//i)*inv[p%i])%p
  return inv

def getCmb(n):
  
  inv = getinv(n)
  
  nCr = [0]*(n+1)
  
  nCr[0] = 1
  for i in range(1,n+1):
    
    nCr[i] = (nCr[i-1]*(n-i+1)*inv[i])%p
  return nCr

def solve(n,a,b,k):
  nCr = getCmb(n)
  ans=0
  for i in range(n+1):
    
    j = (k-a*i)//b
    
    if a*i + b*j == k and 0<=j<=n:
      ans+= (nCr[i]*nCr[j])%p
      ans%= p
  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())
p=998244353
def getinv(n):
  inv=[0]*(n+1)
  for i in range(1,n+1):
    inv[i]=pow(i,p-2,p)
  return inv
def getnCr(n):
  inv=getinv(n)
  nCr=[0]*(n+1)
  nCr[0]=1
  for i in range(1,n+1):
    nCr[i]=(nCr[i-1]*(n-i+1)*inv[i])%p
  return nCr
def solve(n,a,b,k):
  ans=0
  nCr=getnCr(n)
  for i in range(n+1):
    if (k-a*i)<0 or (k-a*i)%b!=0:
      continue
    j=(k-a*i)//b
    if a*i+b*j==k and 0<=j<=n:
      ans+= nCr[i]*nCr[j]
      ans%=p
  return ans
print(solve(n,a,b,k))

Solution (Python):
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, N + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD

N, A, B, K = list(map(int, input().split()))
MOD = 998244353
com = comb(N, MOD)

if A > B:
  A, B = (B, A)
Rk = min(N, K // A)

Ans = 0
for i in range(Rk + 1):
  R = i
  if (K - (A * R)) % B != 0:
    continue
  C = (K - (A * R)) // B
  if C > N:
    continue
  Rc = com.com(N, R)
  Cc = com.com(N, C)
  Ans += (Rc * Cc) % MOD

print(Ans % MOD)

Solution (Python):
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, N + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD

N, A, B, K = list(map(int, input().split()))
MOD = 998244353
com = comb(N, MOD)

if A > B:
  A, B = (B, A)
Rk = min(N, K // A)

Ans = 0
for i in range(Rk + 1):
  R = i
  if (K - (A * R)) % B != 0:
    continue
  C = (K - (A * R)) // B
  if C > N:
    continue
  Rc = com.com(N, R)
  Cc = com.com(N, C)
  Ans += (Rc * Cc) % MOD

print(Ans % MOD)

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

F = [1, 1]
Fi = [1, 1]
I = [0, 1]
for i in range(2, N + 1):
  F.append((F[-1] * i) % MOD)
  I.append(MOD - I[MOD % i] * (MOD // i) % MOD)
  Fi.append(Fi[-1] * I[i] % MOD)

if A > B:
  A, B = (B, A)
Rk = min(N, K // A)

Ans = 0
for i in range(Rk + 1):
  R = i
  if (K - (A * R)) % B != 0:
    continue
  C = (K - (A * R)) // B
  if C > N:
    continue
  Rc = F[N] * (Fi[R] * Fi[N - R] % MOD) % MOD
  Cc = F[N] * (Fi[C] * Fi[N - C] % MOD) % MOD
  Ans += (Rc * Cc) % MOD

print(Ans % MOD)

Solution (Python):
n,a,b,k=map(int,input().split())
p=998244353
def getinv(n):
  inv=[0]*(n+1)
  inv[1]=1
  for i in range(2,n+1):
    inv[i]=(-(p//i)*inv[p%i])%p
  return inv
def getnCr(n):
  inv=getinv(n)
  nCr=[0]*(n+1)
  nCr[0]=1
  for i in range(1,n+1):
    nCr[i]=(nCr[i-1]*(n-i+1)*inv[i])%p
  return nCr
def solve(n,a,b,k):
  ans=0
  nCr=getnCr(n)
  for i in range(n+1):
    if (k-a*i)<0 or (k-a*i)%b!=0:
      continue
    j=(k-a*i)//b
    if a*i+b*j==k and 0<=j<=n:
      ans+= nCr[i]*nCr[j]
      ans%=p
  return ans
print(solve(n,a,b,k))

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

mod = 998244353




fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, n+5):
    fac.append(fac[i-1] * i % mod)
    inv.append(mod - inv[mod%i] * (mod//i) % mod)
    finv.append(finv[i-1] * inv[i] % mod)

def nck(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = 0
for ca in range(n+1):
    cb = (k - a * ca) // b
    if (k - a * ca) % b != 0:
        continue
    ans += nck(n, ca) * nck(n, cb)
    ans %= mod

print(ans)

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

mod = 998244353




fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, n+5):
    fac.append(fac[i-1] * i % mod)
    inv.append(mod - inv[mod%i] * (mod//i) % mod)
    finv.append(finv[i-1] * inv[i] % mod)

def nck(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = 0
for ca in range(n+1):
    cb = (k - a * ca) // b
    if (k - a * ca) % b != 0:
        continue
    ans += nck(n, ca) * nck(n, cb)
    ans %= mod

print(ans)

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

if (A+B)*N < K:
    print(0)
    exit()

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

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

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

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

MOD = 998244353
MAX = 3*10**5+2

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)

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

MOD = 998244353
MAX = 3*10**5+2

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)

Solution (Python):
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

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 j1 in range(n+1):
  if (k-a*j1)%b==0:
    j2=(k-a*j1)//b
    count+=cmb(n,j1,m)*cmb(n,j2,m)
  count%=m
print(count)

Solution (Python):

"""
Created on Sat Mar 16 18:40:19 2019

@author: Yamazaki Kenichi
"""

N,A,B,K = map(int,input().split())
mod = 998244353
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
g1 = [1, 1] 
g2 = [1, 1] 
inv = [0, 1] 
for i in range(2, N+1):
    g1.append((g1[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inv[-1]) % mod)
def a(r,b):
    return cmb(N,r,mod)*cmb(N,b,mod)
ans = 0
R = K//A
for i in range(R+1):
    if (K-A*i)%B == 0:
        ans += a(i,(K-A*i)//B) % mod
print(ans%mod)

Solution (Python):

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


def A():
    return


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 and k-a*x <= n*b:
            y = (k-a*x)//b
            ans += comb(n,x)*comb(n,y)%mod
        ans %= mod
    print(ans)


def C():
    return


def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    B()

Solution (Python):

import sys

MOD = 998244353  

def solve(N: int, A: int, B: int, K: int):
    N_max = 3*10**5

    g1 = [1, 1]

    g2 = [1, 1]

    inv = [0, 1]

    for i in range(2, N_max+1):
        g1.append((g1[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD//i)) % MOD)
        g2.append((g2[-1] * inv[-1]) % MOD)

    ans = 0
    for x in range(N+1):
        if (K-A*x)%B==0:
            y = (K-A*x)//B
            if y<0 or y>N:
                continue
            ans += g1[N]*g2[x]*g2[N-x] * g1[N]*g2[y]*g2[N-y]
            ans %= MOD
    print(ans)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = int(next(tokens))  
    B = int(next(tokens))  
    K = int(next(tokens))  
    solve(N, A, B, K)

if __name__ == '__main__':
    main()

Solution (Python):
n,a,b,k=map(int,input().split())
mod=998244353
factorial=[1]
for i in range(1,n+1):
    factorial.append(factorial[i-1]*i%mod)
inverse=[0]*(n+1)
inverse[-1]=pow(factorial[-1],mod-2,mod)
for i in range(n-1,-1,-1):
    inverse[i]=inverse[i+1]*(i+1)%mod
def comb(n,r):
    if n<r:
        return 0
    return factorial[n]*inverse[r]*inverse[n-r]%mod
ans=0
for i in range(n+1):
    j=(k-a*i)//b
    if a*i+b*j==k and 0<=j<=n:
        ans+=comb(n,i)*comb(n,j)
        ans%=mod
print(ans)

Solution (Python):
MOD = 998244353


def get_inv(n):
    inv = [0] * (n + 1)
    inv[1] = 1

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

    return inv


def get_cmb(n):
    inv = get_inv(n)
    cmb = [0] * (n + 1)
    cmb[0] = 1

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

    return cmb


def solve(n, a, b, k):
    ans = 0
    cmb = get_cmb(n)
    for a_num in range(n + 1):
        b_num = (k - a * a_num) // b
        if (a * a_num + b * b_num == k) and (0 <= b_num <= n):
            ans += (cmb[a_num] * cmb[b_num]) % MOD
            ans %= MOD
    return ans


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


main()

Solution (Python):
N,A,B,K=map(int,input().split())
P=998244353
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Fact[0]=1
Finv[0]=1
for i in range(1,N+1):
    Fact[i]=(i*Fact[i-1])%P
    Finv[i]=(Finv[i-1]*inv(i))%P
def NC(k):
    tmp=(Finv[k]*Finv[N-k])%P
    return (Fact[N]*tmp)%P
ans=0
for s in range(N+1):
    t=(K-s*A)//B
    if s*A+t*B==K and 0<=t<=N:
        ans+=(NC(s)*NC(t))%P
print(ans%P)

Solution (Python):
P=998244353
MAX_N=3*10**5+1
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
Fact=[0 for i in range(MAX_N+1)]
Finv=[0 for i in range(MAX_N+1)]
Fact[0]=1
Finv[0]=1
for i in range(MAX_N):
    Fact[i+1]=(Fact[i]*(i+1))%P
    Finv[i+1]=inv(Fact[i+1])%P
def C(n,k):
    return (Fact[n]*(Finv[k]*Finv[n-k])%P)%P
N,A,B,K=map(int,input().split())
L=[]
for i in range(K//A+1):
    if (K-A*i)%B==0:
        j=(K-A*i)//B
        if 0<=i<=N and 0<=j<=N:
            L.append((i,j))
ans=0
for x,y in L:
    ans+=C(N,x)*C(N,y)
    ans%=P
print(ans)

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

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

for i in range(n+1):
    inv_fact[i] = pow(fact[i],mod-2,mod)
    
def cb(n, k, mod):
    return (fact[n] * inv_fact[k] * inv_fact[n-k]) % mod

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

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

Factorial=[1]*(N+1)
for i in range(1,N+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod

inverseFactorial=[1]*(N+1)
inverseFactorial[N]=power(Factorial[N],mod-2)
for i in range(0,N)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def comb(x,y):
  if x<y:
    return 0
  return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod
      
ans=0  
for i in range(K//A+1):
  if (K-A*i)%B==0:
    j=(K-A*i)//B
    ans+=comb(N,i)*comb(N,j)
    ans%=mod
  

    
print(ans%mod)

Solution (Python):
n,a,b,k=map(int,input().split())
mod=998244353
ans=0
fact=[1]*(n+1)
rev=[1]*(n+1)
fx=lambda a,b:(fact[a]*rev[a-b]*rev[b])%mod
for i in range(1,n+1):
    fact[i]=i*fact[i-1]%mod
    rev[i]=pow(fact[i],mod-2,mod)
for i in range(n+1):
    j,r=divmod((k-a*i),b)
    if r==0 and 0<=j<=n:
      ans+=(fx(n,i)*fx(n,j))%mod
print(ans%mod)

Solution (Python):
n,a,b,k=map(int,input().split())
mod=998244353
s=0
fact=[1]*(n+1)
rev=[1]*(n+1)

for i in range(1,n+1):
    fact[i]=i*fact[i-1]%mod
    rev[i]=pow(fact[i],mod-2,mod)
fx=lambda a,b:(fact[a]*rev[a-b]*rev[b])%mod

for i in range(n+1):
    j,r=divmod((k-a*i),b)
    if r==0 and 0<=j<=n:
      s+=(fx(n,i)*fx(n,j))%mod

print(s%mod)

Solution (Python):



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



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



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

Solution (Python):



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



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



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

Solution (Python):



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



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



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

Solution (Python):





"""
AGC025 B
"""

import itertools
from functools import reduce

cut = 998244353


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


def modInverse(a, b, divmod=divmod):
    r0, r1, s0, s1 = a, b, 1, 0
    while r1 != 0:
        q, rtmp = divmod(r0, r1)
        s0, s1 = s1, s0-q*s1
        r0, r1 = r1, rtmp
    return s0 % b














def GCD(a, b):
    r0, r1 = a, b
    while r1 != 0:
        r0, r1 = r1, r0 % r1
    return r0


binom = [1, n]
tmp = n
for i in range(1, n):
    tmp = (tmp*(n-i) % cut)*modInverse(i+1, cut) % cut
    binom.append(tmp)


a, b = max(a, b), min(a, b)
gcdab = GCD(a, b)
ahat, bhat = a//gcdab, b//gcdab
flag = False
for i in range(0, bhat+1):
    if (k-i*a) % b == 0:
        iinit = i
        flag = True
        break


if not flag:
    print(0)
    exit()

ans = 0
for i in range(iinit, min(n+1, k//a+1), bhat):
    ib, bmod = divmod(k-i*a, b)
    if bmod == 0 and ib <= n:
        ans = (ans+binom[i]*binom[ib]) % cut

print(ans)

Solution (Python):
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)

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

C = [0] * (3 * 10 ** 5 + 5)
rC = [0] * (3 * 10 ** 5 + 5)
MOD = 998244353

C[0] = 1
rC[0] = 1
C[1] = 1
rC[1] = 1
for i in range(2, N + 1):
    C[i] = C[i - 1] * i % MOD

rC[N] = pow(C[N], MOD - 2, MOD)

for i in range(N, 1, -1):
    rC[i - 1] = rC[i] * i % MOD


def calc(n, m):
    return C[n] * rC[n - m] * rC[m] % MOD

num = 0
for i in range(N + 1):
    if (K - A * i) % B == 0:
        j = (K - i * A) // B
        if 0 <= j <= N:
            num += calc(N, i) * calc(N, j)
            num = num % MOD

if K == 0:
    print(1)
else:
    print(num % MOD)

Solution (Python):
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(n+1):
  j=(k-i*a)//b
  if (k-i*a)%b or j<0 or j>n:continue
  q=(q+c[i]*c[j])%m 
print(q%m)

Solution (Python):
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(n+1):
  j=(k-i*a)//b
  if (k-i*a)%b or j<0 or j>n:continue
  q=(q+c[i]*c[j])%m 
print(q%m)

Solution (Python):
n,a,b,k=map(int,input().split())
s=0
m=998244353
f=[1]
r=[1]
 
for i in range(1,n+1):
  f+=[i*f[i-1]%m]
  r+=[pow(f[i],m-2,m)]

cb=lambda x,y:f[x]*r[x-y]*r[y]

for i in range(n+1):
  c,d=divmod(k-a*i,b)
  if d==0 and 0<=c<=n:
    s=(s+cb(n,i)*cb(n,c))%m

print(s)

Solution (Python):

from sys import stdin
import math

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

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)


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 (0 <= (K - i*A) // B <= N):
        ans = (ans + Comb[i]*Comb[(K - i*A) // B]) % NUM 

print(ans)

Solution (Python):
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       

def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac


def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        

def nCr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if not (0<=r and r<=n):
        return 0
    
    return ((fac[n]*facInv[r]) % mod) * facInv[n-r] % mod



MOD = 998244353

n,a,b,k = li()


inv = inv_mod(n,MOD)
fac = fact(n,MOD)
facInv = fact_inv(n,inv,MOD)

ans = 0

for red in range(n+1):
    res = k - red*a
    if res%b != 0:
        continue
    else:
       blue = res//b
       
       ans = (ans + nCr(n,red,MOD,fac,facInv) * nCr(n,blue,MOD,fac,facInv)) % MOD

print(ans)

Solution (Python):
N,A,B,K=map(int,input().split())
P=998244353
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Fact[0]=1
Finv[0]=1
for i in range(1,N+1):
    Fact[i]=(i*Fact[i-1])%P
    Finv[i]=(Finv[i-1]*inv(i))%P
ans=0
def NC(k):
    tmp=(Finv[k]*Finv[N-k])%P
    return (Fact[N]*tmp)%P
for x in range(N+1):
    y=(K-x*A)//B
    if x*A+y*B==K and 0<=y<=N:
        ans+=(NC(x)*NC(y))%P
print(ans%P)

Solution (Python):
N,A,B,K=map(int,input().split())
P=998244353
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Fact[0]=1
Finv[0]=1
for i in range(1,N+1):
    Fact[i]=(i*Fact[i-1])%P
    Finv[i]=(Finv[i-1]*inv(i))%P
ans=0
def NC(k):
    tmp=(Finv[k]*Finv[N-k])%P
    return (Fact[N]*tmp)%P
for x in range(N+1):
    y=(K-x*A)//B
    if x*A+y*B==K and 0<=y<=N:
        ans+=(NC(x)*NC(y))%P
print(ans%P)

Solution (Python):
n,a,b,k=map(int,input().split())
mod=998244353
s=0
fac=[1]*(n+1)
rev=[1]*(n+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):
  j,r=divmod((k-a*i),b)
  if r==0 and 0<=j<=n:
    s+=(f(n,i)*f(n,j))%mod

print(s%mod)

Solution (Python):
N,A,B,K = map(int,input().split())
sprime = 998244353 
A,B = sorted((A,B))
if (A+B) * N < K:
	print(0)
	exit()
 
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 i in range(1,N//2+1):
	v = memo[i-1] * (N-i+1) * modinv(i,sprime)
	v = v % sprime
	memo[i] = memo[N-i] = v
 

sum = 0
for b in range(N+1):
  a = (K-b*B)//A
  if 0 <= a <= N and a*A+b*B == K:
    sum += memo[a]*memo[b]
    sum %= sprime
 
print(sum)

Solution (Python):


MOD = 998244353

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

    return inv

def getCmb(N):
    inv = getInv(N)
    nCr = [0] * (N + 1)
    nCr[0] = 1
    nCr[0] = 1
    
    for i in range(1, N + 1):
        nCr[i] = (nCr[i - 1] * (N - i + 1) * inv[i]) % MOD
    
    return nCr

def solve(N, A, B, K):
    ans = 0
    nCr = getCmb(N)
    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
    return ans
    

if __name__ == "__main__":
    N, A, B, K = map(int, input().split())
    print(solve(N,A,B,K))

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):
import math
import sys
import fractions
inp = input()
N,A,B,K = list(map(int,inp.split()))

g = fractions.gcd(A,B)
if K % g != 0:
    print(0)
    sys.exit()
A = A // g
B = B // g
K = K // g
xn = []
yn = []
for i in range(10 ** 100):
    if (A * i- K) % B == 0:
        n = i
        xn.append(n)
        yn.append((K - A *n) // B)
        break
if yn[-1] < 0:
    if K % B == 0 and (K // B <= N):
        print(1)
    else:
        print(0)
    sys.exit()
while True:
    x  = xn[-1] + B
    y  = yn[-1] - A
    if y < 0:
        break
    xn.append(x)
    yn.append(y)
ans = 0
P = 998244353
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 
 
for x,y in zip(xn,yn):
    if N-x< 0 or N -y < 0:
        continue 
    ans = (ans + (comb(N,x) * comb(N,y))) % P
print(ans)