Problem:


Score : 700 points

Problem Statement

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

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

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

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

Constraints

1 ≤ N ≤ 3×10^5

1 ≤ A,B ≤ 3×10^5

0 ≤ K ≤ 18×10^{10}

All values in the input are integers.

Input

Input is given from Standard Input in the following format:

N A B K

Output

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

Sample Input 1

4 1 2 5

Sample Output 1

40

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

1 green, 1 blue

1 red, 2 blues

2 reds, 1 green

3 reds, 1 blue

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

Sample Input 2

2 5 6 0

Sample Output 2

1

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

Sample Input 3

90081 33447 90629 6391049189

Sample Output 3

577742975



Sample input:
4 1 2 5


Sample output:
40

Submission status: Wrong Answer

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

a_max =  min(k // a, n)
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)

Submission status: Wrong Answer

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

a_max =  min(k // a, n)
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)
print(result % MOD)

Submission status: Wrong Answer

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

a_max =  min(k // a, n)
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
# print(nCr)

print(pair)

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

Submission status: Wrong Answer

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

def squaremod(A,p,mod):#A^p(mod p)の計算
    if p==0:
        return 1
    if p%2==1:
        return (A*squaremod(A,p-1,mod))%mod
    if p%2==0:
        return (squaremod(A,p/2,mod) %mod)**2 %mod

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

Combi=[N]*(N+1)
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+3,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)

Submission status: Wrong Answer

Solution code:
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 y>=0:
			ans+=(ncr(N,x))%mod*(ncr(N,y))%mod

print ans

Submission status: Wrong Answer

Solution code:
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: break
	if (K-A*x)%B==0:
		y=(K-A*x)/B
		ans+=(ncr(N,x))%mod*(ncr(N,y))%mod

print ans

Submission status: Wrong Answer

Solution code:
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
		ans+=(ncr(N,x))%mod*(ncr(N,y))%mod

print ans

Submission status: Wrong Answer

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

if K==0: print 1;quit()

mod=998244353
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, 300001):
    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(1,N+1):
	if (K-A*x)%B==0:
		y=(K-A*x)/B
		ans+=(ncr(N,x))%mod*(ncr(N,y))%mod

print ans

Submission status: Wrong Answer

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

if K==0: print 1;quit()

mod=998244353
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, N+2):
    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(1,N+1):
	if (K-A*x)%B==0:
		y=(K-A*x)/B
		ans+=(ncr(N,x))%mod*(ncr(N,y))%mod

print ans

Submission status: Wrong Answer

Solution code:
from math import factorial

N,A,B,K = map(int, "90081 33447 90629 6391049189".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):
    # return (f[n] * inv[r]) % un * inv[n-r] % un
    return factorial(n) // (factorial(r) * factorial(n - r))

total = 0
for a in range(N+1):
    if((K-A*a)%B==0):
        b = (K-A*a)//B
        total += nCr(N, a) * nCr(N, b)

print(str(total % un))

Submission status: Wrong Answer

Solution code:
N, A, B, K = map(int, input().split())
mod = 998244353
f_table = [1, 1]
inverse_table = [0, 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.append((f_table[-1] * i) % mod)
    inverse_table.append(pow(f_table[-1], mod-2, 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)

Submission status: Wrong Answer

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

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

P = 998244353

N, A, B, K = reads()

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

def egcd(a, b):
  if b == 0:
    return a, 1, 0
  else:
    q, r = divmod(a, b)
    g, x, y = egcd(b, r)
    return g, y, x - q * y

def inv(n):
  g, x, _ = egcd(n, P)
  # assert g == 1
  return x

def comb(n, k):
  # assert 0 <= k <= n
  return fact[n] * inv(fact[k]) * inv(fact[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)

Submission status: Wrong Answer

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

def modc(a,b,m):
    c = 1
    for i in range(b):
        c = c * (a-i) % m
        c = c * modinv(i+1, m)%m
    return c
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 modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m
total = 0
for i in range(n+1):
    if((k-a*i)%b==0):
        count_b = (k-a*i)//b
        total += modc(n, i, un) * modc(n, count_b, un)

print(str(total % un))

Submission status: Wrong Answer

Solution code:
import math

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

N, A, B, K = map(int, input().split())
ans = 0
for a in range(N):
    b = (K - a * A) // B
    if (K - a * A) % B == 0 and 0 <= b <= N:
        ans += combinations_count(N, a) * combinations_count(N, b)
print(ans % 998244353)

Submission status: Wrong Answer

Solution code:
import math


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


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

ans = 0
for a in range(N):
    if a * A > K:
        break
    if (K - a * A) % B == 0 and 0 <= (K - a * A) // B <= N:
        b = (K - a * A) // B
        ans += combinations_count(N, a) * combinations_count(N, b)
print(ans % 998244353)

Submission status: Wrong Answer

Solution code:
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 (K-A*x)%B == 0:
        ans += cmb(N,x,mod)*cmb(N,int(y),mod) % mod
print(ans)

Submission status: Wrong Answer

Solution code:
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 = 10**5*3
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):
    if N >= (K-A*x)/B >= 0 and ((K-A*x)/B).is_integer():
        ans += cmb(N,x,mod)*cmb(N,(K-A*x)//B,mod) % mod
print(ans)

Submission status: Wrong Answer

Solution code:
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 = 10**5*3
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):
    if N >= (K-A*x)/B >= 0 and (K-A*x)/B == int((K-A*x)/B):
        ans += cmb(N,x,mod)*cmb(N,(K-A*x)//B,mod) % mod
print(int(ans))

Submission status: Wrong Answer

Solution code:
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, mod):
    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, mod) * cmb(N, b, mod) % mod
print(res)

Submission status: Wrong Answer

Solution code:
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, mod):
    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 b <= N:
        res += cmb(N, a, mod) * cmb(N, b, mod) % mod
print(res)

Submission status: Wrong Answer

Solution code:
import math

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


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
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)

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
def comb(a,b):
    if a==0 or b==0:
        return 1
    ans=1
    for i in range(b):
        ans*=a-i
        ans//=(i+1)
    return ans
n,a,b,k=map(int,input().split())
x=0
y=0
ans=0
while x<=n:
    if (k-a*x)%b==0:
        ans+=comb(n,x)*comb(n,(k-a*x)//b)
        ans%=998244353
    x+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

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


ANS=0

ran=K//A

for i in range(min(ran,N)+1):
    if (K-(A*i))%B==0:
        if (K-(A*i))//B<=N:
            ANS = (ANS+(Combi(N,i)*Combi(N,(K-(A*i))//B)))%998244353
        else:
            break


print(ANS)

Submission status: Wrong Answer

Solution code:
import math

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

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


ANS=0

ran=K//A

for i in range(min(ran,N)):
    if (K-(A*i))%B==0 and (K-(A*i))//B>0 and (K-(A*i))//B<N:
        ANS += (Combi(N,i)*Combi(N,(K-(A*i))//B))%998244353
 


print(ANS)

Submission status: Wrong Answer

Solution code:
global MOD
MOD = 998244353

def modInverse(a,p):
    return pow(a,p-2,p)

def nCr(n,r,p):
    num = 1
    for i in range(r):
        num = (num * (n-i)) % p

    den = 1
    for i in range(1,r+1):
        den = (den * i) % p

    return (num * modInverse(den,p)) % p

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

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

Submission status: Wrong Answer

Solution code:
#from scipy.misc import comb
n, a, b, k = map(int,input().split())	

modN = 998244353
 
def preparef(n, MOD): 
  fn = [1] * (n + 1)
  f = 1
  for m in range(1, n + 1):
    f *= m
    f %= MOD
    fn[m] = 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

fn, invs = preparef(n, modN)

def comb(n,k,f):
  # f is not used
  return (fn[n] * invs[k]) % modN * invs[n-k] % modN
 
ret = 0
for i in range(n+1):
  if (a * i - k) % b == 0 :
    na = i
    nb = (-1) * ((a * i - k) // b)
    if nb >= 0 and nb <= n:
      ret += (comb(n,na,1) * comb(n,nb,1)) % modN

print(ret)

Submission status: Wrong Answer

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

modN = 998244353
 
def preparef(n, MOD): 
  fn = [1] * (n + 1)
  f = 1
  for m in range(1, n + 1):
    f *= m
    f %= MOD
    fn[m] = 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

fn, invs = preparef(n, modN)

def comb(n,k,f):
  # f is not used
  return (fn[n] * invs[k]) % modN * invs[n-k] % modN
 
ret = 0
for i in range(n):
  if (a * i - k) % b == 0 :
    na = i
    nb = (-1) * ((a * i - k) // b)
    if nb >= 0 and nb <= n:
      ret += (comb(n,na,1) * comb(n,nb,1)) % modN

print(ret)

Submission status: Wrong Answer

Solution code:
N = 3*10**5
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
print(ans)

Submission status: Wrong Answer

Solution code:
N = 3*10**5
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 >= 0 and x%b == 0:
        j = x//b
        ans += nCk(n, i) * nCk(n, j) % MOD
print(ans)

Submission status: Wrong Answer

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

print(ncr)
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)

Submission status: Wrong Answer

Solution code:
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): # 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
def ncr(n,r):
    if n <= r: return 0
    if mem[r] > 0:
        return mem[r]
    else:
        ret = mul(mul(fac[n], inv(fac[n-r])), inv(fac[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
    ans += mul(ncr(N,a), ncr(N,b))
print(ans % MOD)

Submission status: Wrong Answer

Solution code:
import math
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n;

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p;
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result;

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

print(ans)

Submission status: Wrong Answer

Solution code:
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 (K-A*i)%B==0 and j <= N:
        j //= B
        n+=memo[i]*memo[j]
        n%=998244353
print(n%998244353)

Submission status: Wrong Answer

Solution code:
import itertools


if __name__ == '__main__':
    N, A, B, K = map(int, input().split())
    li = [i for i in range(N)]
    ans = 0
    for ai in range(N):
        tmp = K-(ai*A)
        if tmp / B <= N and tmp % B == 0:
            bi = tmp // B
            a = len(list(itertools.combinations(li, ai)))
            b = len(list(itertools.combinations(li, bi)))
            ans += a*b
    print(ans)

Submission status: Wrong Answer

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

MOD = 998244353
p = [1, 1]
q = [1, 1]
for i in range(2, n+1):
    p.append(p[-1]*i%MOD)
    q.append(pow(p[-1], MOD-2, MOD))

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

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

Submission status: Wrong Answer

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

X = set()
for n in range(0, K//A+1):
    m = (K - n * A) // B
    if n <= N and m <= N and n * A + m * B == K:
        X.add((n, m))

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

ans = 0
for n, m in X:
    ans += comb[n] * comb[m]
    ans = ans % M
print(ans)

Submission status: Wrong Answer

Solution code:
N,A,B,K = map(int,input().split())
sprime = 998244353 # approx 10**9
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
 
# max is A*N + B*N
sum = 0
for j in range(0,N):
	i = (K-B*j)//A
	if 0 <= i <= N and A*i+B*j==K:
		sum += memo[i] * memo[j]
		sum %= sprime
 
print(sum)

Submission status: Wrong Answer

Solution code:
L = input().split()
sprime = 998244353 # approx 10**9
N = int(L[0])
A = int(L[1])
B = int(L[2])
K = int(L[3])

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

# max is A*N + B*N
sum = 0
for i in range(0,N):
	if (K - A*i) % B == 0:
		j = (K-A*i)//B
		if 0 <= j <= N:
			sum += memo[i] * memo[j]
			sum %= sprime

print(sum)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

L = input().split()
sprime = 998244353 # approx 10**9
N = int(L[0])
A = int(L[1])
B = int(L[2])
K = int(L[3])

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

# max is A*N + B*N
sum = 0
for i in range(0,N):
	if (K - A*i) % B == 0:
		j = (K-A*i)//B
		if 0 <= j <= N:
			sum += memo[i] * memo[j]
			sum %= sprime

print(sum)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

L = input().split()
sprime = 998244353 # approx 10**9
N = int(L[0])
A = int(L[1])
B = int(L[2])
K = int(L[3])

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

# max is A*N + B*N
sum = 0
for i in range(0,N):
	if (K - A*i) % B == 0:
		j = (K-A*i)//B
		if 0 <= j <= N:
			sum += (memo[i] * memo[j]) % sprime

print(sum)

Submission status: Wrong Answer

Solution code:
def combo(m,n):
    ans=1
    for i in range(n+1,m+1):
        ans*=i
    for i in range(1,(m-n+1)):
        ans=ans//i
    return ans

num=input().split()
N=int(num[0])
A=int(num[1])
B=int(num[2])
K=int(num[3])
res=0
tim=min(K//A,N)

for i in range(0,tim+1):
    if (K-i*A)%B==0:
        m=i
        n=(K-i*A)//B
        if m+n>2*N:
            break
        res+=combo(N,m)*combo(N,n)
        res=res%998244353
print(res)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

L = input().split()
sprime = 998244353 # approx 10**9
N = int(L[0])
A = int(L[1])
B = int(L[2])
K = int(L[3])

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

# max is A*N + B*N
sum = 0
for i in range(0,N):
	if (K - A*i) % B == 0:
		j = (K-A*i)//B
		if 0 <= j <= N:
			sum += (memo[i] * memo[j]) % sprime

print(sum)

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb
N,A,B,K = map(int, input().split())
count = 0
P = []
c = 0
while c < N:
  if K % B == 0:
    if K//B <= N:
      #print((c, K//B))
      P.append([c, K//B])
  K -= A
  c += 1
for p in P:
 count += comb(N, p[0], exact=True) * comb(N, p[1], exact=True)
if count > 998244353:
  count = count % 998244353
print(count)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

L = input().split()
sprime = 998244353 # approx 10**9
N = int(L[0])
A = int(L[1])
B = int(L[2])
K = int(L[3])

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

@lru_cache(maxsize=N)
def factorial(m):
	a = 1
	for i in range(1,m):
		a = (a*i) % sprime
	return a

def binom(m):
	if N == m:
		return 1
	elif m == 1:
		return N
	elif m > N:
		return 0
	else:
		return (factorial(N) * modinv(factorial(m),sprime) * modinv(factorial(N-m),sprime)) % sprime

# max is A*N + B*N
sum = 0
for i in range(0,N):
	if (K - A*i) % B == 0:
		j = (K-A*i)//B
		sum += (binom(i) * binom(j)) % sprime

print(sum)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split();
    [N, A, B, K] = [long(input_raw[0]), long(input_raw[1]), long(input_raw[2]), long(input_raw[3])]
    li = []
    for t in range(N + 1):
        if (K - t * A)%B == 0:
            u = (K - t * A)/B
            for y in range(t + u - N, N + 1):
                x = t - y
                z = u - y
                w = N -(x + y + z)
                if w >= 0 and x >= 0 and y >= 0 and z >= 0:
                    li.append((w, x, y, z))

                    #print w, x, y, z
                    #print x * A + y *(A + B) + z * B
    frac_N = [0 for i in range(N + 1)]
    power_N = [0 for i in range(N + 1)]
    frac_N[0] = 1
    power_N[0] = 1
    p = 998244353L
    for i in range(1, N + 1):
        frac_N[i] = (frac_N[i - 1] * i ) % p
        power_N[i] = power_func(frac_N[i], p - 2, p)

    print len(li)
    s = 0L
    for i in range(len(li)):
        w = li[i][0]
        x = li[i][1]
        y = li[i][2]
        z = li[i][3]
        s = (s + (frac_N[N] * power_N[x] * power_N[y] * power_N[z] * power_N[w])) % p
    print s


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import factorial

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

success=[]
for i in range(int(K/a)):
    if (K-a*i)%b==0:
        success.append((i,int((K-a*i)/b)))

result=[]
for s in success:
    for z in list(range(min(s)))[::-1]:
        x=s[0]-z
        y=s[1]-z
        if x+y+z>n:break
        result.append((x,y,z))

def func(a,b,c,n):
    return int((factorial(n)%998244353)/(factorial(a)*factorial(b)*factorial(c)*factorial(n-a-b-c)))

final=0
for r in result:
    final+=func(r[0],r[1],r[2],n)
    if final>998244353:
        final=final%998244353

print(final)