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: Accepted

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

Submission status: Accepted

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

LARGE = 998244353
INVS = [0]*(N+1)
for i in range(1, N+1):
    INVS[i] = pow(i, LARGE-2, LARGE)
NCKL = [1]*(N+1)
for i in range(1, N+1):
    NCKL[i] = (NCKL[i-1] * (N+1-i) * INVS[i]) % LARGE

res = 0
for i in range(N+1):
    if (K - A*i) % B == 0:
        j = (K - A*i) // B
        if j >= 0 and j <= N:
            res += (NCKL[i] * NCKL[j]) % LARGE
print(res % LARGE)

Submission status: Runtime Error

Solution code:
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
        ans += cmb(N,i)*cmb(N,j)
        ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
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 and rest % B == 0:
        b = rest // B
        tmp = combi(N, a) * combi(N, b) % MOD
        ans += tmp
        ans %= MOD
print(ans)

Submission status: Runtime Error

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


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=10**9+7

F=FactMod(N+1,MOD)

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

Submission status: Runtime Error

Solution code:
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
        res += f.comb(N, i) * f.comb(N, j)
        res %= MOD
        
print(res)

Submission status: Runtime Error

Solution code:
import math

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

p = 0
for a in range(N+1):
    if (K -(A*a)) % B == 0:
        b = (K -(A*a)) // B
        if 0 <= b <= N:
            p += (math.factorial(N))**2/(math.factorial(a)*math.factorial(b)*math.factorial(N-a)*math.factorial(N-b))

print(p % 998244353)

Submission status: Runtime Error

Solution code:
import math

N, A, B, K = map(int, input().split())
a_1 = K % A
a_2 = K // A
b_1 = K % B
b_2 = K // B
c = math.gcd(A, B)

p = 0
if K == 0:
    p = 1
else:
    if a_1 == 0:
        p += math.factorial(N)/(math.factorial(K//A)*math.factorial(N-(K//A)))
    if b_1 == 0:
        p += math.factorial(N)/(math.factorial(K//B)*math.factorial(N-(K//B)))


    if b_1 == 0:
        i = 1
        while (B*(i)) % A != 0:
            i += 1
    else:
        i = 0
        while (b_1 + B*i) % A != 0:
            i += 1
    Ai = (b_1 + B*i) / A
    Bi = b_2 - i
    while Bi > 0:
        for g in range(min(Ai,Bi)+1):
            p += math.factorial(N)/(math.factorial(Ai-g)*math.factorial(Bi-g)*math.factorial(g)*math.factorial(N-Ai-Bi+g))
        Ai += (B/c)
        Bi -= (A/c)

print(p % 998244353)

Submission status: Runtime Error

Solution code:
import math

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

p = 0
if K == 0:
    p = 1
else:
    for r in range(K//A+1):
        for b in range((K-(A*r))//B+1):
            if r == 0 and B * b == K:
                p += math.factorial(N)/(math.factorial(b)*math.factorial(N-b))
            elif b == 0 and A * r == K:
                p += math.factorial(N)/(math.factorial(r)*math.factorial(N-r))
            elif A*r + B*b == K:
                for g in range(min(r,b)+1):
                    Red = r - g
                    Blue = b - g
                    p += math.factorial(N)/(math.factorial(Red)*math.factorial(Blue)*math.factorial(g)*math.factorial(N-Red-Blue-g))

print(p % 998244353)

Submission status: Runtime Error

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

if k == 0:
    print(1)
    exit()
    
MOD = 998244353
N = 5 * 10**5

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD


ans = 0
for i in range(n):
    if i * a > k or (k - (i * a)) % b != 0:
        continue
    j = (k - (i * a)) // b
    ans += comb(n, i) * comb(n, j)
    ans %= MOD

print(ans)

Submission status: Runtime Error

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


MOD = 998244353
N = 5 * 10**5

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD


ans = 0
for i in range(n):
    if i * a > k or (k - (i * a)) % b != 0:
        continue
    j = (k - (i * a)) // b
    ans += comb(n, i) * comb(n,j)
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
N,A,B,K=map(int,input().split())
p=998244353
fracmod=[1]*(N+1)
fracmodinv=[1]*(N+1)
ans=0
i=0
j=0
for i in range(1,N+1):
    fracmod[i]=(fracmod[i-1]*i)%p
#print(fracmod[:6])
for i in range(N+1):
    fracmodinv[i]=modinv(fracmod[i],p)
for i in range(N+1):
    forb=K-i*A      #bに割く得点
    if (forb%B==0)and(forb//B>=0):
        j=forb//B
        #print(i,j)
        ans=(ans+((((fracmod[N]*fracmodinv[N-i]*fracmodinv[i])%p)*(fracmod[N]*fracmodinv[N-j]*fracmodinv[j]))%p))%p
print(ans)

Submission status: Runtime Error

Solution code:
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
N,A,B,K=map(int,input().split())
p=998244353
fracmod=[1]*(N+1)
fracmodinv=[1]*(N+1)
ans=0
i=0
j=0
for i in range(1,N+1):
    fracmod[i]=(fracmod[i-1]*i)%p
#print(fracmod[:6])
for i in range(N+1):
    fracmodinv[i]=modinv(fracmod[i],p)
for i in range(N+1):
    forb=K-i*A      #bに割く得点
    if forb%B==0:
        j=forb//B
        #print(i,j)
        ans=(ans+((((fracmod[N]*fracmodinv[N-i]*fracmodinv[i])%p)*(fracmod[N]*fracmodinv[N-j]*fracmodinv[j]))%p))%p
print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd

N, A, B, K = map(int, input().split())
if K == 0:
    print(1)
    exit()
c = gcd(A, B)
if K % c != 0:
    print(0)
    exit()
A //= c; B //= c; K //= c
mod = 998244353

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


ans = 0
for x in range(N+1):
    if (K - A * x) % B != 0:
        continue
    y = (K - A * x) // B
    tmp = 0
    for g in range(max(0, x + y - N), min(x, y, N)+1):
        r = x - g
        b = y - g
        if r < 0 or b < 0:
            break
        tmp = (tmp + fact_inv[r] * fact_inv[b] * fact_inv[g] * fact_inv[N - r - g - b]) % mod
    ans = (ans + tmp) % mod
ans = ans * fact[N] % mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, a, b, k = list(map(int, readline().split()))
    M = 998244353

    h = (n + 1) // 2
    l = h + 1
    com = [0] * l
    com[0] = 1

    for i in range(1, l):
        t = com[i - 1] * (n + 1 - i)
        t *= pow(i, M - 2, M)
        t %= M
        com[i] = t

    ans = 0
    rng = min(k // a + 1, n)

    for x in range(rng):
        res = k - a * x
        if res % b == 0:
            y = res // b
            if x > h:
                x = n - x
            if y > h:
                y = n - y

            add = com[x] * com[y]
            ans += add
            ans %= M

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
mod = 998244353

def comb(n, r):
    if 2 * r > n: return comb(n, n-r)
    return fac[n] * inv[r] * inv[n-r] % mod

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

n_max = 3*10**5
fac = [1] * (n_max+2)
inv = [1] * (n_max+2)
for i in range(2, n+1):
    fac[i] = fac[i-1] * i % mod
inv[n] = pow(fac[n], mod - 2, mod)
for i in range(n-1, 1, -1):
    inv[i] = inv[i + 1] * (i + 1) % mod

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

print(ans)

Submission status: Runtime Error

Solution code:
mod = 998244353

def comb(n, r):
    if 2 * r > n: return comb(n, n-r)
    return fac[n] * inv[r] * inv[n-r] % mod

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
mod = 998244353

def comb(n, r):
    if 2 * r > n: return comb(n, n-r)
    return fac[n] * inv[r] * inv[n-r] % mod

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
n,a,b,k=map(int,input().split())
mod=998244353
ans=0
p=[1]*(n+1)
for i in range(n):
    p[i+1]=((i+1)*p[i])%mod
for ai in range(n+1):
    if k-a*ai>=0 and (k-a*ai)%b==0:
        bi=(k-a*ai)//b
        ans+=p[n]*pow(p[ai],mod-2,mod)*pow(p[n-ai],mod-2,mod)*p[n]*pow(p[bi],mod-2,mod)*pow(p[n-bi],mod-2,mod)
        ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
n,a,b,k=map(int,input().split())
mod=998244353
ans=0
p=[1]*(n+1)
for i in range(n):
    p[i+1]=((i+1)*p[i])%mod
for ai in range(n+1):
    if k-a*ai>=0 and (k-a*ai)%b==0:
        bi=(k-a*ai)//b
        ans+=p[n]*pow(p[ai],mod-2,mod)*pow(p[n-ai],mod-2,mod)
        ans%=mod
        ans+=p[n]*pow(p[bi],mod-2,mod)*pow(p[n-bi],mod-2,mod)
        ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy


N,A,B,K=map(int,input().split())
mod=998244353
Fac=[0 for i in range(N+1)]
iFac=[0 for i in range(len(Fac))]
Fac[0]=1
Fac[1]=1
for i in range(2,N+1):
    Fac[i]=i*Fac[i-1]%mod
for i in range(N+1):
    iFac[i]=pow(Fac[i],mod-2,mod)
lst=[]
for a in range(N+1):
    value=(K-a*A)
    if value%B==0:
        lst.append([a,value//B])

def comb(x,y):
    if x==0 or y==0:
        return(1)
    else:
        return(Fac[x]*iFac[x-y]%mod*iFac[y]%mod)



count=0
for a,b in lst:
    for i in range(a+b-N,min(a,b)+1):
        if a+b-i<=N:
            count+=Fac[N]*iFac[a-i]%mod*iFac[b-i]%mod*iFac[i]%mod*iFac[N-a-b+i]%mod
            count%=mod
        #if i<=50000:

        #    count+=comb(N,a-i) * comb(N-(a-i),b-i)  * comb(N-(a-i)-(b-i),i)

print(count)

Submission status: Runtime Error

Solution code:
mod = 998244353
N, A, B, K = map(int, input().split())
def make_fact(n):#0~nの階乗を求める
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i%mod
    return fact
fact = make_fact(N) #＠
def make_fact_inv(n):#0~nの階乗のmodに関する逆元を求める
    fact_inv = [1]*(n+1)
    fact_inv[n] = pow(fact[n], mod-2, mod)#フェルマーの小定理
    for i in range(n, 0, -1):
        fact_inv[i-1] = fact_inv[i]*i%mod
    return fact_inv
fact_inv = make_fact_inv(N)#＠
def comb(n, k):#nCk
    return fact[n]*fact_inv[k]*fact_inv[n-k]%mod
ans = 0
for k in range(N+1):
    r = K-k*A
    if r%B != 0 or r//B>N:
        continue
    l = r//B
    ans+=comb(N, k)*comb(N, l)
    ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0


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

c = Factorial(N + 1, MOD).comb

def calc(a, b):
    return (c(N, a) * c(N, b)) % MOD

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

print (ans)

Submission status: Runtime Error

Solution code:
def mod_cmb(n, r, mod=10 ** 9 + 7):
	assert n >= r >= 0

	def ex_euclid(x, y):
		a, b = 1, 0
		while y != 0:
			a, b = b, (a - x // y * b)
			x, y = y, x % y
		return a

	p = q = 1
	for i in range(n - r + 1, n + 1):
		p *= i
		p %= mod
	for i in range(2, r + 1):
		q *= i
		q %= mod
	p *= ex_euclid(q, mod)
	p %= mod
	return p

N, A, B, K = map(int, input().split())
mod = 998244353
ans = 0
for r in range(N + 1):
	if (K - A * r) % B == 0:
		ans += mod_cmb(N, r, mod) * mod_cmb(N, (K - A * r) // B, mod)
		ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce

def cmb(n, r):
	if n < r: return 0
	if r == 0 or n - r == 0: return 1
	r = min(n - r, r)
	u = reduce(mul, range(n, n - r, -1))
	d = reduce(mul, range(1, r + 1))
	return u // d % mod

N, A, B, K = map(int, input().split())
mod = 998244353
ans = 0
for r in range(N + 1):
	if (K - A * r) % B == 0:
		ans += cmb(N, r) * cmb(N, (K - A * r) // B)
		ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random  # randome is not available at Codeforces
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

import sys
sys.setrecursionlimit(10**7)
mo=998244353


n,a,b,k=LI()


f=[0]*(2+n)
r=[0]*(2+n)

def fact(n):
    if n==0:
        f[0]=1
        return 1
    if f[n]!=0:
        return f[n]
    f[n]=n*fact(n-1)%mo
    return f[n]

r[n]=pow(fact(n),mo-2,mo)

def revfact(n):
    if r[n]!=0:
        return r[n]
    r[n]=( (n+1)*revfact(n+1) )%mo
    return r[n]

def comb(n,k):
    return fact(n)*revfact(n-k)*revfact(k)%mo


fact(n)
revfact(0)

show_flg=False
show_flg=True

if a<b:
    a,b=b,a
ans=0
for i in range(min(n+1,k//a+1)):
    if (k-a*i)%b!=0 and 0<=((k-a*i)//b)<=n:
        continue
    j=(k-a*i)//b
    ans+=comb(n,i)*comb(n,j)
    ans%=mo

print(ans%mo)

Submission status: Runtime Error

Solution code:
from fractions import gcd

class PERM_COMB_MOD():
    # http://drken1215.hatenablog.com/entry/2018/06/08/210000
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

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

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

mod = 998244353
n,a,b,k = map(int, input().split())
if k % gcd(a,b) != 0:
    print(0)
    exit()
hoge = PERM_COMB_MOD(n=n+10, mod=mod)
ans = 0
for i in range(n+1):
    tmp = k-a*i
    if tmp % b:
        continue
    j = tmp//b
    if j < 0 or n < j:
        continue
    ans += hoge.comb(n, i)*hoge.comb(n, j)
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
MOD = 998244353
MAX = int(3e5 + 10)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


def main():
    N, A, B, K = map(int, input().split())
    ans = 0
    # solve Ax + By = K
    for x in range(N+1):
        By = K - x * A
        if By >= 0 and By % B == 0:
            y = By // B
            tmp1 = FACT[N] * INV[x] * INV[N-x] % MOD
            tmp2 = FACT[N] * INV[y] * INV[N-y] % MOD
            ans = (ans + tmp1 * tmp2) % MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
MOD = 998244353
MAX = int(3e5 + 1)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


def main():
    N, A, B, K = map(int, input().split())
    ans = 0
    for x in range(N+1):
        By = K - x * A
        if By >= 0 and By % B == 0:
            y = By // B
            tmp1 = FACT[N] * INV[x] * INV[N-x] % MOD
            tmp2 = FACT[N] * INV[y] * INV[N-y] % MOD
            ans = (ans + tmp1 * tmp2) % MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
class Combination:
    '''
    計算量：階乗・逆元テーブルの作成O(N)
            nCkを求めるO(1)
    '''

    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [pow(self.fact[i] ,MOD - 2 ,MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        '''k!を求める'''
        return self.fact[k]

    def inverse_factorial(self, k):
        '''k!の逆元を求める'''
        return self.inv_fact[k]

    def combination(self, k, r):
        '''kCrを求める'''
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


n, a, b, k = map(int, input().split())
MOD = 998244353
comb = Combination(n, MOD)
ans = 0
for i in range(n+1):
    if not(k - a*i >= 0 and (k - a*i) % b == 0 and (k - a*i) % b <= n):
        continue
    else:
        ai = i
        bi = (k - a*i) // b
        ans += comb.combination(n, ai) * comb.combination(n, bi)
        ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)

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
            bpatt = (factorial[N] * revfactorial[N - b] * revfactorial[b]) % mod
            ans += (apatt * bpatt) % mod
            ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
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
            bpatt = (factorial[N] * revfactorial[N - b] * revfactorial[b]) % mod
            ans += (apatt * bpatt) % mod
            ans %= mod
print(ans)

Submission status: Runtime Error

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

def pow(n, i):
    if i == 1: return n
    else:
        if 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) % mod
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
            bpatt = (factorial[N] * revfactorial[N - b] * revfactorial[b]) % mod
            ans += (apatt * bpatt) % mod
            ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
p=998244353
def getinv(n):
  inv = [0]*(n+1)
  #フェルマーの小定理より、a=1の時は1であることが分かる
  inv[1] = 1
  for i in range(2,n+1):
    #そのまま計算すると負になってしまうので、最後にmod pを取ることで正に戻す
    inv[i] = (-(p//a)*inv[p%a])%p
  return inv

def getCmb(n):
  #逆元を取得
  inv = getinv(n)
  #0 <= r <= n に対してnCrを求める
  nCr = [0]*(n+1)
  #r=0の時は、r-1が存在しないので与えておく
  nCr[0] = 1
  for i in range(1,n+1):
    #iで割る代わりにinv[i]をかけ、mod pを求める
    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):
    #割り切れない時もあるが、その時は次の条件a*i+b*j==kで弾かれるので問題ない
    j = (k-a*i)//b
    #条件に一致するものを選ぶ。jの範囲に注意
    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))

Submission status: Runtime Error

Solution code:
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:
      ans+= nCr[i]*nCr[j]
      ans%=p
  return ans
print(solve(n,a,b,k))

Submission status: Runtime Error

Solution code:
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:
      print(i)
      print(j)
      ans+= nCr[i]*nCr[j]
      ans%=p
  return ans
print(solve(n,a,b,k))

Submission status: Runtime Error

Solution code:
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)%b!=0:
      continue
    j=(k-a*i)//b
    if a*i+b*j==k:
      ans+=(nCr[i]*nCr[j])%p
      ans%=p
  return ans
print(solve(n,a,b,k))

Submission status: Runtime Error

Solution code:
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):
    j=(k-a*i)//b
    if a*i+b*j==k:
      ans+=nCr[i]+nCr[j]
      ans%=p
  return ans
print(solve(n,a,b,k))

Submission status: Runtime Error

Solution code:
from math import factorial
n,a,b,k=map(int,input().split())
def gcd(x,y):
  if y==0:
    return x
  else:
    return gcd(y,x%y)
ans=0
p=998244353
x=gcd(a,b)
if k%x==0:
  A=a//x
  B=b//x
  K=k//x
  for i in range(n):
    if K-A*i>=0 and (K-A*i)%B==0:
      ans+= (((factorial(n)//factorial(n-i)//factorial(i))%p)*((factorial(n)//factorial(n-(K-A*i)//B)//factorial((K-A*i)//B))%p))%p
      ans=ans%p
print(ans)

Submission status: Runtime Error

Solution code:
from math import factorial
n,a,b,k=map(int,input().split())
def gcd(x,y):
  if y==0:
    return x
  else:
    return gcd(y,x%y)
ans=0
p=998244353
x=gcd(a,b)
if K%x==0:
  A=a//x
  B=b//x
  K=k//x
  for i in range(n):
    if (K-A*i)%B==0:
      ans+= (factorial(n)//factorial(n-i)//factorial(i))*(factorial(n)//factorial(n-(K-A*i)//B)//factorial((K-A*i)//B))
print(ans)

Submission status: Runtime Error

Solution code:
import math
n,a,b,k=map(int,input().split())
def gcd(x,y):
  if y==0:
    return x
  else:
    return gcd(y,x%y)
p=gcd(a,b)
ans=0
for i in range(k//(a+b)):
  if (k-(a+b)*i)%p!=0:
    continue
  else:
    q=gcd(p,k-(a+b)*i)
    A=a//q
    B=b//q
    K=k//q
    A_=(pow(A,B-2,B)*K)%p
    for i in range((n-i-A_)//B):
      ans+=math.factorial(n-i)//(math.factorial(A_+B*i)*math.factorial((k-A_+B*i)//B)*math.factorial(n-i-A_+B*i-(k-A_+B*i)//B))
print(ans)

Submission status: Runtime Error

Solution code:
from math import factorial as fac
def cc(n,r):
  return fac(n)//fac(r)//fac(n-r)
n, a, b, k = map(int, input().split())
mod = 998244353
for i in range(min(k//a+1,n+1)):
  j = k-a*i
  if j%b == 0 andj<=n:
    ans += cc(n,i)*cc(n,j)%mod
    ans %= mod
print(ans)