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):
def nCr(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 
size = 10**6 
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, size + 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 = map(int,input().split())
ans = 0
for k in range(N + 1):
    if A * k > K:
        break
    if (K - A * k) % B != 0:
        continue
    l = (K - A * k) // B
    ans += nCr(N,k,mod) * nCr(N,l,mod)
    ans %= mod
print(ans)

Solution (Python):
mod = 998244353
N,A,B,K = map(int,input().split())
def cmb(n,k):
    return fac[n]*inv_fac[n-k]*inv_fac[k] % mod
fac = [1]
for i in range(1,N+1):
    fac.append(fac[-1]*i % mod)
inv_fac = [pow(fac[N],mod-2,mod)]
for i in range(1,N+1)[::-1]:
    inv_fac.append(inv_fac[-1]*i % mod)
inv_fac = inv_fac[::-1]

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

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

fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,n+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

def nPr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[n-r]%mod


ans = 0
for i in range(n+1):
    if i*a > k:
        break
    d = k-i*a
    if d%b or d//b > n:
        continue
    ans += nCr(n,i,mod)*nCr(n,d//b,mod)%mod
    ans %= mod
print(ans)

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

MOD = 998244353
N = n + 10
fact = [0 for _ in range(N)]
invfact = [0 for _ in range(N)]
fact[0] = 1
for i in range(1, N):
    fact[i] = fact[i - 1] * i % MOD

invfact[N - 1] = pow(fact[N - 1], MOD - 2, MOD)

for i in range(N - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD
def nCk(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return fact[n] * invfact[k] * invfact[n - k] % MOD
        
ans = 0
for i in range(n + 1):
    j = (kk - a * i)
    if j % b != 0:
        continue
    ans += nCk(n, i) * nCk(n, j // b)
    ans %= MOD
    
print(ans)

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

MOD = 998244353
factorials = [1]
inv_facts = [1]
for i in range(1, N+1):
    factorials.append(factorials[-1] * i % MOD)
    inv_facts.append(inv_facts[-1] * pow(i, MOD-2, MOD) % MOD)

def combi(n, k):
    ret = factorials[n]
    ret *= inv_facts[k]
    ret %= MOD
    ret *= inv_facts[n-k]
    ret %= MOD
    return ret

ans = 0
for a in range(N+1):
    rest = K - (A * a)
    if rest < 0:
        break
    if rest % B == 0:
        b = rest // B
        if b <= N:
            tmp = combi(N, a) * combi(N, b) % MOD
            ans += tmp
            ans %= MOD
print(ans)

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


N = 3*10**5
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 
def cmb(n,r,mod=998244353):
    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)

def main():
    ans = 0
    n,a,b,k = map(int,ipt().split())
    for xa in range(n+1):
        if (k-a*xa)%b == 0:
            xb = (k-a*xa)//b
            if 0 <= xb <= n:
                ans += cmb(n,xa)*cmb(n,xb)

    print(ans%mod)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	n,a,b,k=MI()

	m=998244353

	C=[1]
	for i in range(n):
		t=C[-1]*(n-i)*pow(i+1,m-2,m)
		C.append(t%m)
	

	ans=0

	for x in range(n+1):
		if (k-a*x)%b==0:
			y=(k-a*x)//b
			if 0<=y<=n:
				ans+=C[x]*C[y]
				ans%=m
	print(ans)

























if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	n,a,b,k=MI()

	m=998244353

	C=[1]
	for i in range(n):
		t=C[-1]*(n-i)*pow(i+1,m-2,m)
		C.append(t%m)
	

	ans=0

	for x in range(n+1):
		if (k-a*x)%b==0:
			y=(k-a*x)//b
			if 0<=y<=n:
				ans+=C[x]*C[y]
				ans%=m
	print(ans)

























if __name__ == "__main__":
	main()

Solution (Python):



import math
mod = 998244353


class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def C(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def P(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod


def main():
    N, A, B, K = map(int, input().split())
    c = Combi(N, mod)    
    res = 0
    for i in range(N+1):
        if (K-A*i) % B == 0 and K >= A*i:
            res += c.C(N, i)*c.C(N, (K-A*i)//B)
    res %= mod
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 998244353

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

    a = [None] * (N+1)
    inva = [None] * (N+1)
    a[0] = 1
    
    for i in range(1, N+1):
        a[i] = i * a[i-1] % m
    
    inva[N] = pow(a[N],m-2,m)
    for i in range(N):
        inva[N-i-1] = inva[N-i] * (N-i) % m

    ans = 0
    for i in range(N+1):
        if (K-A*i) % B == 0:
            j = (K-A*i)//B
            if 0 <= j <= N:
                tmp1 = (a[N] * inva[i] % m) * inva[N-i] % m
                tmp2 = (a[N] * inva[j] % m) * inva[N-j] % m
                ans += tmp1 * tmp2 % m
                ans %= m
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def combs_mod(n,k,mod):
  
  inv = [1]*(k+1)
  for i in range(1,k+1):
    inv[i] = pow(i,mod-2,mod)
  ans = [1]*(k+1)
  for i in range(1,k+1):
    ans[i] = ans[i-1]*(n+1-i)*inv[i]%mod
  return ans
def solve():
  mod = 998244353
  N, A, B, K = map(int, input().split())
  com = combs_mod(N,N,mod)
  ans = 0
  for x in range(N+1):
    if (K-A*x)%B==0:
      y = (K-A*x)//B
      if y>=0 and y<=N:
        ans += com[x]*com[y]
        ans %= mod
  return ans
print(solve())

Solution (Python):
MAX = 3*10**5+100
MOD = 998244353
fact = [0]*MAX 
inv = [0]*MAX 
finv = [0]*MAX 
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD

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

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

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

print(ans)

Solution (Python):

MOD = 998244353

class Factorial:
    def __init__(self, n, mod):
        self.f = f =[0] * (n + 1)
        f[0] = b = 1
        for i in range(1, n + 1):
            f[i] = b = b * i % mod
        self.inv = inv = [0] * (n + 1)
        inv[n] = b = pow(self.f[n], -1, mod)
        for i in range(n, 0, -1):
            inv[i - 1] = b = b * i % mod
        self.mod = mod

    def factorial(self, i):
        return self.f[i]

    def ifactorial(self, i):
        return self.inv[i]

    def C(self, n, k):
        if not 0 <= k <= n: return 0
        return self.f[n] * self.inv[n - k] * self.inv[k] % self.mod

    def P(self, n, k):
        if not 0 <= k <= n: return 0
        return self.f[n] * self.inv[n - k] % self.mod

    def H(self, n, k):
        if (n == 0 and k > 0) or k < 0: return 0
        return self.f[n + k - 1] * self.inv[k] % self.mod * self.inv[n - 1] % self.mod



n, a, b, k = map(int, input().split())
F = Factorial(n, MOD)
c = 0
for p in range(k // a + 1):
    q, _ = divmod(k - p*a, b)
    if _:continue
    c = (c + F.C(n, p) * F.C(n, q)) % MOD
print(c)

Solution (Python):
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] 
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 func(na,nb):
  if 0<=na<=n and 0<=nb<=n:
    ret=1
    ret*=cmb(n,na,mod)
    ret%=mod
    ret*=cmb(n,nb,mod)
    ret%=mod
    return ret
  else:
    return 0
ans=0
for na in range(n+1):
  if (k-na*a)%b==0:
    ans+=func(na,(k-na*a)//b)
    ans%=mod
print(ans)

Solution (Python):
n,a,b,k=map(int,input().split())
mod=998244353
import math
def lcm(x, y):
  return (x * y) // math.gcd(x, y)
g=math.gcd(a,b)
if k%g!=0:
  print(0)
  exit()
k//=g
a//=g
b//=g


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] 
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 func(na,nb):
  ret=1
  ret*=cmb(n,na,mod)
  ret%=mod
  ret*=cmb(n,nb,mod)
  ret%=mod
  return ret

def func0(na,nb):
  ret=0
  if na<nb:na,nb=nb,na
  for nc in range(min(nb,n)+1):
    
    reti=1
    if 0<=nc<=n and 0<=na-nc<=n and  0<=nb-nc<=n:
      reti*=g1[n]
      reti%=mod
      reti*=g2[nc]
      reti%=mod
      reti*=g2[na-nc]
      reti%=mod
      reti*=g2[nb-nc]
      reti%=mod
      reti*=g2[n+nc-na-nb]
      reti%=mod
      ret+=reti
  return ret
pat=[]
for i in range(1+k//a):
  if (k-a*i)%b==0:
    pat.append([i,(k-a*i)//b])
    break
na=pat[0][0]
nb=pat[0][1]
while nb-a>=0:
  na+=b
  nb-=a
  pat.append([na,nb])
ans=0
for na,nb in pat:
  if na>n or nb>n:continue
  ans+=func(na,nb)
  ans%=mod
print(ans)

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

Solution (Python):
n,a,b,k=map(int,input().split())
mod1,mod2=10**9+7,998244353
mod=mod2
fact=[1]*(n+1)
inv=[1]*(n+1)
for i in range(2,n+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n,1,-1):
    inv[i-1]=inv[i]*i%mod
def comb(x,y):return fact[x]*inv[y]%mod*inv[x-y]%mod if x>=y>=0 else 0
ans=0
for i in range(n+1):
    if (k-(a*i))%b:continue
    o=(k-(a*i))//b
    ans=(ans+comb(n,i)*comb(n,o)%mod)%mod
print(ans)

Solution (Python):






import sys
readline = sys.stdin.readline

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

DIV = 998244353
n = (10 ** 6) * 2 
g1 = [1] * 2 + [0] * (n - 2) 
g2 = [1] * 2 + [0] * (n - 2) 
inverse = [0, 1] + [0] * (n - 2) 

for i in range(2, n):
  g1[i] = (g1[i - 1] * i) % DIV
  inverse[i] = (-inverse[DIV % i] * (DIV // i)) % DIV
  g2[i] = (g2[i - 1] * inverse[i]) % DIV

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


ans = 0
for a in range(N + 1):
  rest = K - a * A
  if rest < 0:
    break 
  if rest % B != 0:
    continue 
  b = rest // B
  if b > N:
    continue 
  
  
  ans += (nCr(N, a, DIV) * nCr(N, b, DIV)) % DIV
  ans %= DIV
  
print(ans)

Solution (Python):






import sys
readline = sys.stdin.readline

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

DIV = 998244353
n = (10 ** 6) * 2 
g1 = [1] * 2 + [0] * (n - 2) 
g2 = [1] * 2 + [0] * (n - 2) 
inverse = [0, 1] + [0] * (n - 2) 

for i in range(2, n):
  g1[i] = (g1[i - 1] * i) % DIV
  inverse[i] = (-inverse[DIV % i] * (DIV // i)) % DIV
  g2[i] = (g2[i - 1] * inverse[i]) % DIV

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


ans = 0
for a in range(N + 1):
  b = K - a * A
  if b < 0:
    break 
  if b % B != 0:
    continue 
  if (b // B) > N:
    continue 
  
  
  ans += (nCr(N, a, DIV) * nCr(N, b // B, DIV)) % DIV
  ans %= DIV
  
print(ans)

Solution (Python):
from math import gcd

MOD = 998244353

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


inv = [1, 1]
comb_N = [1, N]
for i in range(2, N//2 + 3):
    inv.append(-inv[MOD%i] * (MOD//i) % MOD)
    comb_N.append(comb_N[-1] * (N-i+1) * inv[i] % MOD)


g = gcd(A, B)
if K % g != 0:
    print(0)
    exit()

a = A // g
b = B // g
k = K // g



for n in range(A):
    if (K - B * n) % A == 0:
        m = (K - B * n) // A
        break


if m > N:
    times = -((N - m) // b) 
    m -= b * times
    n += a * times

ans = 0
while m >= 0 and n <= N:
    ans += comb_N[min(m, N-m)] * comb_N[min(n, N-n)] % MOD
    ans %= MOD
    m -= b
    n += a
    
print(ans)

Solution (Python):



class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret

N,A,B,K = map(int,input().split())
ans=0
MOD=998244353

F=FactMod(N+1,MOD)

for a in range(N+1):
    Ascore = a*A
    Bscore=K-Ascore
    if Bscore%B==0:
        b=Bscore//B
        if 0<=b<=N:
            ans+=(F.comb(N,a)*F.comb(N,b))%MOD
            ans%=MOD
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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



M = 998244353 
N = n+10 

g1 = [None] * (N+1) 
g2 = [None] * (N+1) 
inverse = [None] * (N+1) 
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

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

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


def gcd2(a, b):
    """a*x + b*y = gcd(a,b)なるx,yも求める
    """
    l = []
    while b:
        l.append(divmod(a,b))
        a, b = b, a%b
    x, y = 1, 0
    for aa,bb in l[::-1]:
        x, y = y, x - aa*y
    return a, x, y
g,xa,xb = gcd2(a,b)

if k%g!=0:
    ans = 0
else:
    va, vb = xa*(k//g), xb*(k//g)
    l = a*b//g
    if vb<0:
        tmp = abs(vb)//(l//b) + int(abs(vb)//(l//b)!=0)
        vb += tmp*(l//b)
        va -= tmp*(l//a)
    elif vb>0:
        tmp = abs(vb)//(l//b)
        vb -= tmp*(l//b)
        va += tmp*(l//a)
    init = (va,vb)
    ans = 0
    while va>=0:

        assert va*a + vb*b == k
        ans += cmb(n, va, M) * cmb(n, vb,M)
        ans %= M
        va -= l//a
        vb += l//b
print(ans)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=998244353
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

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

N = 10**6
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 )

ans=0
for i in range(n+1):
    aka=i
    if k-aka*a>=0 and (k-aka*a)%b==0:
        ao=(k-aka*a)//b
    else:
        continue
    ans+=cmb(n,aka)*cmb(n,ao)
    ans%=mod
print(ans)

Solution (Python):
n, a, b, k = map(int, input().split())
m = n // 2 + 1
mod = 998244353
comb = [1] * m
for i in range(1, m):
    comb[i] = comb[i - 1] * (n + 1 - i) * pow(i, mod - 2, mod)
    comb[i] %= mod
ans = 0
for i in range(n + 1):
    if a * i > k:
        break
    j = k - a * i
    if j % b == 0:
        j //= b
        if 0 <= j <= n:
            i, j = min(i, n - i), min(j, n - j)
            ans += comb[i] * comb[j]
            ans %= mod
print(ans)

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 998244353

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def comb(n,a,R):
    return (fact[n]*modinv2(fact[n-a]*fact[a],R))

def factinit(n,R):
    global fact
    fact = [1]*(n+1)
    for i in range(2,n+1):
        fact[i] = (fact[i-1]*i)%R


n,a,b,k = inm()
sm = 0
factinit(n,R)
for pq in range(n+1):
    if k<a*pq or (k-a*pq)%b>0:
        continue
    qr = (k-a*pq)//b
    if qr>n:
        continue
    sm = (sm+comb(n,pq,R)*comb(n,qr,R))%R
print(sm)

Solution (Python):










import sys

def input(): return sys.stdin.readline()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip("\n") for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]

def OutH(lst): print(*lst)
def OutV(lst): print(*lst, sep="\n")

sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1

INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)









class Factorial:

    def __init__(self, N):
        self.fact = [0] * (N+1)
        self.fact_inv = [0] * (N+1)
        self.calc_factorial(N)
        self.calc_inv_factorial(N)

    def calc_factorial(self, N):
        self.fact[0] = 1
        for i in range(N):
            self.fact[i+1] = self.fact[i] * (i+1) % MOD

    def calc_inv_factorial(self, N):
        self.fact_inv[N] = pow(self.fact[N], MOD-2, MOD)
        for i in range(N, 0, -1):
            self.fact_inv[i-1] = self.fact_inv[i] * i % MOD

    def comb(self, n, r):
        if (n < 0 or r < 0 or n < r): return 0
        res = self.fact[n]
        res = res * self.fact_inv[r] % MOD
        res = res * self.fact_inv[n-r] % MOD
        return res

    def perm(self, n, r):
        if (n < 0 or r < 0 or n < r): return 0
        res = self.fact[n]
        res = res * self.fact_inv[r] % MOD
        return res

MOD = 998244353

N, A, B, K = iInM()

fac = Factorial(300000)

ans = 0
for a in range(N+1):
    if (K - A * a) % B == 0:
        b = (K - A * a) // B
        ans = (ans + fac.comb(N, a) * fac.comb(N, b)) % MOD
    else:
        continue

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 998244353
    

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

    def extgcd1(a0,b0):
        u,v,a,b=1,0,a0,b0
        while b: t=a//b; a-=t*b; a,b=b,a; u,v=v,u-t*v
        if a!=1: return -1
        return u%b0
    
    maxn=N
    fact=[1]*(maxn+1)
    ifact=[1]*(maxn+1)
    x=1
    for i in range(2,maxn+1):
        x=(x*i)%mod
        fact[i]=x; ifact[i]=extgcd1(x,mod)
        
    def comb(n,r): return (fact[n]*ifact[r]%mod)*ifact[n-r]%mod
    ans=0
    for i in range(N+1):
        b=K-A*i
        if b<0:break
        d,x=divmod(b,B)
        if x!=0 or d>N:
            continue
        ans+=comb(N,i)*comb(N,d)%mod
        ans%=mod
    print(ans)
        





if __name__ == "__main__":
    main()

Solution (Python):
class Factorial():
    def __init__(self, n, mod):
        self.mod = mod
        self.fct = [0 for _ in range(n + 1)]
        self.inv = [0 for _ in range(n + 1)]
        self.fct[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.fct[i + 1] = self.fct[i] * (i + 1) % mod
        self.inv[n] = pow(self.fct[n], mod - 2, mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i + 1] * (i + 1) % mod

    def comb(self, m, k):
        if m < k: return 0
        return self.fct[m] * self.inv[k] * self.inv[m - k] % self.mod

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

f = Factorial(N, MOD)

res = 0

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

print(res)

Solution (Python):
class Factorial():
    def __init__(self, n, mod):
        self.mod = mod
        self.fct = [0 for _ in range(n + 1)]
        self.inv = [0 for _ in range(n + 1)]
        self.fct[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.fct[i + 1] = self.fct[i] * (i + 1) % mod
        self.inv[n] = pow(self.fct[n], mod - 2, mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i + 1] * (i + 1) % mod

    def comb(self, m, k):
        if m < k: return 0
        return self.fct[m] * self.inv[k] * self.inv[m - k] % self.mod

def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
    while c1:
        a0, a1 = a1, a0 - c0 // c1 * a1
        b0, b1 = b1, b0 - c0 // c1 * b1
        c0, c1 = c1, c0 % c1
    return c0, a0, b0

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

f = Factorial(N, MOD)
c, a, b = ex_euclid(A, B)

if K == 0:
    print(1)

elif K % c != 0:
    print(0)

else:
    lo = -10**18
    hi = 10**18
    while hi - lo > 1:
        mid = (hi + lo) // 2
        if a * K // c + mid * B // c >= 0:
            hi = mid
        else:
            lo = mid
    x0 = a * K // c + hi * B // c

    lo = -10**18
    hi = 10**18
    while hi - lo > 1:
        mid = (hi + lo) // 2
        if b * K // c - mid * A // c >= 0:
            lo = mid
        else:
            hi = mid
    y0 = b * K // c - lo * A // c

    res = 0
    x = x0
    y = (K - A * x0) // B

    while True:
        res += f.comb(N, x) * f.comb(N, y)
        res %= MOD
        if y == y0:
            break
        x += B // c
        y -= A // c

    print(res)

Solution (Python):
class Factorial():
    def __init__(self, n, mod):
        self.mod = mod
        self.fct = [0 for _ in range(n + 1)]
        self.inv = [0 for _ in range(n + 1)]
        self.fct[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.fct[i + 1] = self.fct[i] * (i + 1) % mod
        self.inv[n] = pow(self.fct[n], mod - 2, mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i + 1] * (i + 1) % mod

    def comb(self, m, k):
        if m < k: return 0
        return self.fct[m] * self.inv[k] * self.inv[m - k] % self.mod

def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
    while c1:
        a0, a1 = a1, a0 - c0 // c1 * a1
        b0, b1 = b1, b0 - c0 // c1 * b1
        c0, c1 = c1, c0 % c1
    return c0, a0, b0

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

f = Factorial(N, MOD)
c, a, b = ex_euclid(A, B)

if K == 0:
    print(1)

elif K % c != 0:
    print(0)

else:
    lo = -10**18
    hi = 10**18
    while hi - lo > 1:
        mid = (hi + lo) // 2
        if a * K // c + mid * B // c >= 0:
            hi = mid
        else:
            lo = mid
    x0 = a * K // c + hi * B // c

    lo = -10**18
    hi = 10**18
    while hi - lo > 1:
        mid = (hi + lo) // 2
        if b * K // c - mid * A // c >= 0:
            lo = mid
        else:
            hi = mid
    y0 = b * K // c - lo * A // c

    res = 0
    x = x0
    y = (K - A * x0) // B

    while True:
        res += f.comb(N, x) * f.comb(N, y)
        res %= MOD
        if y == y0:
            break
        x += B // c
        y -= A // c

    print(res)

Solution (Python):
from collections import defaultdict
mod = 998244353



max = 3 * 10**5 + 100
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,max):
      fac[i] = fac[i-1]* i% mod
      inv[i] = mod - inv[mod%i] * (mod // i) % mod
      finv[i] = finv[i-1] * inv[i] % mod

comInit(max)


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

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

red = defaultdict(int)
for i in range(n+1):
    red[i*a] = com(n,i)

ans = 0
for i in range(n+1):
    point = k - b*i
    if(point < 0):
        break
    ans += red[point] * com(n,i)
    ans %= mod

print(ans)

Solution (Python):
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

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

p = 998244353
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans = 0

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

print(ans%p)

Solution (Python):
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

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

p = 998244353
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans = 0

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

print(ans%p)

Solution (Python):
M=998244353;n,A,B,K=map(int,input().split());F=[1];a=0
for i in range(n):F+=[F[-1]*(n-i)*pow(i+1,M-2,M)%M]
for i in range(n+1):
 r=K-i*A
 if r%B==0and 0<=r//B<=n:a+=F[i]*F[r//B]
print(a%M)

Solution (Python):
M=998244353;n,A,B,K=map(int,input().split());F=[1];a=0
for i in range(n):F+=[F[-1]*(n-i)*pow(i+1,M-2,M)%M]
for i in range(n+1):
 r=K-i*A;q=r//B
 if(r%B==0)&(0<=q<=n):a+=F[i]*F[q]
print(a%M)

Solution (Python):
M=998244353;n,A,B,K=map(int,input().split());F=[1];a=0
for i in range(n):F+=[F[-1]*(n-i)*pow(i+1,M-2,M)%M]
for i in range(n+1):
 q,r=divmod(K-i*A,B)
 if(r==0)&(0<=q<=n):a+=F[i]*F[q]
print(a%M)