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: Runtime Error

Solution code:
import math
import sys
inp = input()
N,A,B,K = list(map(int,inp.split()))
g = math.gcd(A,B)
if K % g != 0:
    print(0)
    sys.exit()
A = A // g
B = B // g
K = K // g
xn = []
yn = []
for i in range(10 ** 100):
    if (A * i- K) % B == 0:
        n = i
        xn.append(n)
        yn.append((K - A *n) // B)
        break
if yn[-1] < 0:
    if K % B == 0 and (K // B <= N):
        print(1)
    else:
        print(0)
    sys.exit()
while True:
    x  = xn[-1] + B
    y  = yn[-1] - A
    if y < 0:
        break
    xn.append(x)
    yn.append(y)
ans = 0
P = 998244353
def inv(n):
  return pow(n, P-2, P)
fact = [1] * (N+1)
for i in range(1, N+1):
  fact[i] = fact[i-1] * i % P
invfact = [inv(fact[N])] * (N+1)
for i in range(N, 0, -1):
  invfact[i-1] = invfact[i] * i % P
def comb(n, k):
  return fact[n] * invfact[k] * invfact[n-k] % P 
 
for x,y in zip(xn,yn):
    if N-x< 0 or N -y < 0:
        continue 
    ans = (ans + (comb(N,x) * comb(N,y)) % P)
print(ans)

Submission status: Runtime Error

Solution code:
import math
import sys
x = input()
N,A,B,K = list(map(int,x.split()))
g = math.gcd(A,B)
if K % g != 0:
    print(0)
    sys.exit()
A = A // g
B = B // g
K = K // g
xn = []
yn = []
for i in range(10 ** 100):
    if (A * i- K) % B == 0:
        n = i
        xn.append(n)
        yn.append((K - A *n) // B)
        break
if yn[-1] < 0:
    if K % B == 0 and (K // B <= N):
        print(1)
    else:
        print(0)
    sys.exit()
while True:
    x  = xn[-1] + B
    y  = yn[-1] - A
    if y < 0:
        break
    xn.append(x)
    yn.append(y)
ans = 0
P = 998244353
def inv(n):
  return pow(n, P-2, P)
fact = [1] * (N+1)
for i in range(1, N+1):
  fact[i] = fact[i-1] * i % P
invfact = [inv(fact[N])] * (N+1)
for i in range(N, 0, -1):
  invfact[i-1] = invfact[i] * i % P
def comb(n, k):
  return fact[n] * invfact[k] * invfact[n-k] % P 

for x,y in zip(xn,yn):
    if N-x< 0 or N -y < 0:
        continue 
    ans = (ans + (comb(N,x) * comb(N,y)) % P)
print(ans)

Submission status: Runtime Error

Solution code:

# your code goes here
n,a,b,k= map(int,input().split())

w = [1]
for i in range(0,n//2):
    w.append(w[-1]*(n-i)//(i+1))
if n %2 ==0:
    for i in range(0,n//2):
        w.append(w[(n-2)//2-i])
else:
    for i in range(0,n//2):
    	w.append(w[(n-3)//2-i])


c = 0
if k//a >= n:
    x = n
else:
    x = k //a

if k == 0:
    c = 1
else:
    for h in range(0,x+1):
        i = (k-a*h)/b

        if i == int(i) and n >= i:
            c += w[h]*w[int(i)]

print(c%998244353)

Submission status: Runtime Error

Solution code:
import math
n,a,b,k= map(int,input().split())
w = []


w = [1]
for i in range(0,n):
    w.append(w[-1](n-i)//(i+1)% 998244353)
#コンビネーションw[i] = nCi


c = 0
if k//a >= n:
    x = n
else:
    x = k //a

if k == 0:
    c = 1
else:
    for h in range(0,x+1):
        i = (k-ah)/b

        if i == int(i) and n >= i:
            c = w[h]*w[int(i)]%998244353+c

print(c%998244353)

Submission status: Runtime Error

Solution code:

import math
n,a,b,k= map(int,input().split())	
def w(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
#コンビネーション


c = 0
if k//a >= n:
    x = n
else:
    x = k //a
for h in range(0,x+1):
    i = (k-a*h)/b
    
    if 2*n >= h + int(i) and i == int(i):
        c = w(n,h)*w(n,int(i))+c
if c == 0:
    c = 1
print(c%998244353)

Submission status: Runtime Error

Solution code:
fact_list=[None]*300001
inv_fact_list=[None]*300001
fact_list[0]=1
inv_fact_list[0]=1

def inv(n):
    if inv_fact_list[n]!=None:
        return inv_fact_list[n]
    m=fact_list[n]
    s=1
    for i in range(30):
        if i!=23 and i!=26:
            s=(s*m)%998244353
        m=(m**2)%998244353
    inv_fact_list[n]=s
    return s
"""
def enc(n):
    if n==0:
        return "("
    s=""
    while n>0:
        s+=chr(n%86+40)
        n//=86
    return s

def dec(s):
    n=0
    for i in range(len(s)):
        n+=(86**i)*(ord(s[i])-40)
    return n
def comb(n,r):
    if r==0 or r==n:
        return 1
    if r==1 or r==n-1:
        return n
    if inv_fact_list[n-r]!=None:
        invnr=inv_fact_list[n-r]
    else:
        m=fact_list[n-r]
        invnr=1
        for i in range(30):
            if i!=23 and i!=26:
                invnr=(invnr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[n-r]=invnr
    if inv_fact_list[r]!=None:
        invr=inv_fact_list[r]
    else:
        m=fact_list[r]
        invr=1
        for i in range(30):
            if i!=23 and i!=26:
                invr=(invr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[r]=invr
    return (((fact_list[n]*invnr)%998244353)*invr)%998244353
"""

for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353

s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
if b>a:
    a,b=b,a
for i in range(n):
    if k-a*i<0:
        break
    j=(k-a*i)//b
    if (k-a*i)%b==0 and 0<=j<=n:
        res=(res+(fact_list[n]**2)*inv((((fact_list[i]*fact_list[j]%998244353)*fact_list[n-i]%998244353)*fact_list[n-j]%998244353)))%998244353
print(res)

Submission status: Runtime Error

Solution code:
fact_list=[None]*300001
inv_fact_list=[None]*300001
fact_list[0]=1
inv_fact_list[0]=1

def inv(n):
    if inv_fact_list[n]!=None:
        return inv_fact_list[n]
    m=fact_list[n]
    s=1
    for i in range(30):
        if i!=23 and i!=26:
            s=(s*m)%998244353
        m=(m**2)%998244353
    inv_fact_list[n]=s
    return s
"""
def enc(n):
    if n==0:
        return "("
    s=""
    while n>0:
        s+=chr(n%86+40)
        n//=86
    return s

def dec(s):
    n=0
    for i in range(len(s)):
        n+=(86**i)*(ord(s[i])-40)
    return n
def comb(n,r):
    if r==0 or r==n:
        return 1
    if r==1 or r==n-1:
        return n
    if inv_fact_list[n-r]!=None:
        invnr=inv_fact_list[n-r]
    else:
        m=fact_list[n-r]
        invnr=1
        for i in range(30):
            if i!=23 and i!=26:
                invnr=(invnr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[n-r]=invnr
    if inv_fact_list[r]!=None:
        invr=inv_fact_list[r]
    else:
        m=fact_list[r]
        invr=1
        for i in range(30):
            if i!=23 and i!=26:
                invr=(invr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[r]=invr
    return (((fact_list[n]*invnr)%998244353)*invr)%998244353
"""

for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353

s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
if b>a:
    a,b=b,a
for i in range(n):
    if k-a*i<0:
        break
    j=(k-a*i)//b
    if (k-a*i)%b==0 and 0<=j<=n:
        res=(res+(fact_list[n]**2)*inv((((fact_list[i]*fact_list[j]%998244353)*fact_list[n-i]%998244353)*fact_list[n-j]%998244353))%998244353
print(res)

Submission status: Runtime Error

Solution code:
def comb(r):
    if r==0 or r==n:
        return 1
    if r==1 or r==n-1:
        return n
    if inv_fact_list[n-r]!=None:
        invnr=inv_fact_list[n-r]
    else:
        m=fact_list[n-r]
        invnr=1
        for i in range(30):
            if i!=23 and i!=26:
                invnr=(invnr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[n-r]=invnr
    if inv_fact_list[r]!=None:
        invr=inv_fact_list[r]
    else:
        m=fact_list[r]
        invr=1
        for i in range(30):
            if i!=23 and i!=26:
                invr=(invr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[r]=invr
    return (((fact_list[n]*invnr))*invr)%998244353

for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353

s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
if b>a:
    a,b=b,a
for i in range(n):
    if k-a*i<0:
        break
    if (k-a*i)%b==0 and 0<=(k-a*i)//b<=n:
        res=(res+comb(i)*comb((k-a*i)//b))%998244353
print(res)

Submission status: Runtime Error

Solution code:
fact_list=[None]*300001
inv_fact_list=[None]*300001
fact_list[0]=1
inv_fact_list[0]=1
def inv(n):
    if inv_fact_list[n]!=None:
        return inv_fact_list[n]
    n=fact_list[n]
    s=1
    for i in range(30):
        if i!=23 and i!=26:
            s=(s*n)%998244353
        n=(n**2)%998244353
    inv_fact_list[n]=s
    return s

def comb(n,r):
    if r==0 or r==n:
        return 1
    if r==1 or r==n-1:
        return n
    return (((fact_list[n]*inv(n-r))%998244353)*inv(r))%998244353

for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353

s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
for i in range(n+1):
    if k-a*i<0:
        break
    if (k-a*i)%b==0 and 0<=(k-a*i)//b<=n:
        res=(res+comb(n,i)*comb(n,(k-a*i)//b))%998244353
print(res)

Submission status: Runtime Error

Solution code:
fact_list=[None]*300001
inv_fact_list=[None]*300001
fact_list[0]=1
inv_fact_list[0]=1
def inv(n):
    if inv_fact_list[n]!=None:
        return inv_fact_list[n]
    s=1
    for i in range(30):
        if i!=23 and i!=26:
            s=(s*n)%998244353
        n=(n**2)%998244353
    inv_fact_list[n]=s
    return s

def comb(n,r):
    if r==0 or r==n:
        return 1
    if r==1 or r==n-1:
        return n
    return (((fact_list[n]*inv(fact_list[n-r]))%998244353)*inv(fact_list[r]))%998244353

for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353

s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
for i in range(n+1):
    if k-a*i<0:
        break
    if (k-a*i)%b==0 and 0<=(k-a*i)//b<=n:
        res=(res+comb(n,i)*comb(n,(k-a*i)//b))%998244353
print(res)

"""
def enc(n):
    if n==0:
        return "("
    s=""
    while n>0:
        s+=chr(n%86+40)
        n//=86
    return s

def dec(s):
    n=0
    for i in range(len(s)):
        n+=(86**i)*(ord(s[i])-40)
    return n
"""

Submission status: Runtime Error

Solution code:
def comb(n,r):
    return (((fact_list[n]*inv(fact_list[n-r]))%998244353)*inv(fact_list[r]))%998244353
def inv(n):
    s=1
    for i in range(30):
        if i!=23 and i!=26:
            s=(s*n)%998244353
        n=(n**2)%998244353
    return s

fact_list=[1 for i in range(300001)]
for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353

s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
for i in range(n):
    if (k-a*i)%b==0 and (k-a*i)//b<=n:
        res+=comb(n,i)*comb(n,(k-a*i)//b)
        res%=998244353
print(res)

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys, math, copy
from functools import lru_cache
# import fractions, itertools
# import numpy as np
# import scipy
sys.setrecursionlimit(10 ** 6)

MOD = 998244353
HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

@lru_cache(maxsize=10 ** 6)
def fact(i):
    if i <= 1:
        return 1
    return i * fact(i - 1) % MOD

def combi(n, i):
    return fact(n) // (fact(i) * fact(n - i))

def main():
    n, a, b, k = map(int, input().split())
    print(n, a, b, k)
    res = 0
    for i in range(0, n + 1):
        residual = k - a * i
        if residual < 0:
            continue
        if residual % b > 0:
            continue
        j = residual // b
        res += combi(n, i) * combi(n, j)
        res %= MOD
    print(res)

main()

Submission status: Runtime Error

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

def cdiv(x,y):
  if x % y == 0: return x/y
  else: return x/y + 1

ly = [0, cdiv(k - a*n, b), -1]
ry = [n, k/b, -1]

if b > a:
  ly[2] = cdiv(k - 2*a*n , b - a)
  ry[2] = (k - a*n) / (b - a)
else:
  ly[2] = cdiv(k - a*n, b - a)
  ry[2] = (k - 2*a*n) / (b - a)

l, r = max(ly), min(ry)
if l <= r: print r - l + 1
else: print 0

Submission status: Runtime Error

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

def cdiv(x,y):
  if x % y == 0: return x/y
  else: return x/y + 1

ly = [0, cdiv(k - a*n, b), -1]
ry = [n, k/b, -1]

if b > a:
  ly[3] = cdiv(k - 2*a*n , b - a)
  ry[3] = (k - a*n) / (b - a)
else:
  ly[3] = cdiv(k - a*n, b - a)
  ry[3] = (k - 2*a*n) / (b - a)

l, r = max(ly), min(ry)
if l <= r: print r - l + 1
else: print 0

Submission status: Runtime Error

Solution code:
import math

DIV_NUM = 998244353

def comb(c, d):
    return ( math.factorial(c) // (math.factorial(c - d) * math.factorial(d)) )

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

result = 0

i = 0
j = 0
for i in range(n + 1):
    if k < a * i:
        break
    if ( k - a * i ) % b == 0:
        j = ( k - a * i ) // b
        result += comb(n, i) * comb(n, j)
        result %= DIV_NUM

print(result)

Submission status: Runtime Error

Solution code:
#coding : utf8

import math
import itertools


def drawColors(N, A, B, K):

    allCom = 0
    l = range(1, N+1)
    for i in range(1, N+1):
        red_score = A*i
        blue_score = K - red_score
        redCount = 0
        blueCount = 0

        if( (blue_score%B) == 0 ):
            j = int(blue_score/B)
            for elem in itertools.combinations(l, i):
                redCount += 1
            for elem in itertools.combinations(l, j):
                blueCount += 1

            allCom += ((redCount * blueCount)%998244353)
            # redCom = (math.factorial(N)/(math.factorial(i)*math.factorial(N-i)))%998244353
            # blueCom = (math.factorial(N)/(math.factorial(j)*math.factorial(N-j)))%998244353

    if( allCom == 0):
        allCom = 1

    return allCom

if __name__ == '__main__':

    # N A B K
    # N : towerHight
    # A : score
    # B : score
    # K : beauty(scoreSum)
    li = list(map(int, input().split()))

    result = drawColors(li[0], li[1], li[2], li[3])
    print(int(result))

Submission status: Runtime Error

Solution code:
from functools import lru_cache
from fractions import gcd


n, a, b, k = map(int, input().split())
b, a = max(a, b), min(a, b)
q = 998244353

n_ = n % q
d = gcd(a, b)
ans = 0

 
def init_mod_inv(n, q):
    mod_inv = [0, 1]
    for i in range(2, n + 1):
        inv = q - (q // i) * mod_inv[q % i] % q
        mod_inv.append(inv)
    return mod_inv
        
mod_inv = init_mod_inv(n_, q)

def gen_nCr(n, q, mod_inv):
    nCr = [1]
    for i in range(1, n+1):
        nCr.append((nCr[i - 1] * (n - i + 1) * mod_inv[i]) % q)
    return nCr
nCr = gen_nCr(n, q, mod_inv)


j = -1
for i in range(min(n, k // a) + 1):
    res = k - i * a
    #if res < 0:
    #    break
    if res % b == 0:
        j = i
        break
for i in range(j, min(n, k // a) + 1, b // d):
    res = k - i * a
    ans += (nCr[i % q] * nCr[(res // b) % q]) % q
            
print(ans)

Submission status: Runtime Error

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

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


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

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


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

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

    print(com)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# https://beta.atcoder.jp/contests/agc025/tasks/agc025_b
from functools import reduce
import operator as op

MOD = 998244353
mod_inv = [0, 1]


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


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

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

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# https://beta.atcoder.jp/contests/agc025/tasks/agc025_b
from functools import reduce
import operator as op

MOD = 998244353
mod_inv = [0, 1]


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


def nCr(n, r):
    r = min(r, n - r)
    ans = 1
    for i in range(n, n - r, -1):
        ans = (ans * i) % MOD
    for i in range(1, r + 1):
        ans = (mod_inv[i] * ans) % MOD
    return ans

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

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from math import factorial

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

def get_comb(a):
  b = (K-A*a)/B
  if b.is_integer() and b <= N:
    comb_a = factorial(N) // (factorial(N - a) * factorial(a))
    comb_b = factorial(N) // (factorial(N - b) * factorial(b))   
    return comb_a*comb_b
  else:
    return 0

print(sum([get_comb(a) for a in range(N+1)]) % 998244353)

Submission status: Runtime Error

Solution code:
from math import factorial

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

def get_comb(a):
  b = (K-A*a)/B
  if b.is_integer() and b <= N:
    comb_a = factorial(N) // (factorial(N - a) * factorial(a))
    comb_b = factorial(N) // (factorial(N - b) * factorial(b))   
    return comb_a*comb_b
  else:
    return 0

print(sum([get_comb(a) for a in range(N+1)]))

Submission status: Runtime Error

Solution code:

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

mod = 998244353
F = [1]
RF = []


def inv(x):
    res = 1
    k = mod - 2
    y = x
    while k:
        if k & 1:
            res = (res * y) % mod
        y = (y * y) % mod
        k //= 2
    return res


def init():
    for i in range(N):
        F.append((F[i] * (i + 1)) % mod)
    for i in F:
        RF.append(inv(i))


def comb(x, y):
    return (F[x] * ((inv(F[x - y]) * inv(F[y])) % mod)) % mod


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

Submission status: Runtime Error

Solution code:

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

mod = 998244353
F = [1]
RF = []


def inv(x):
    res = 1
    k = mod - 2
    y = x
    while k:
        if k & 1:
            res = (res * y) % mod
        y = (y * y) % mod
        k //= 2
    return res


def init():
    for i in range(N):
        F.append((F[i] * (i + 1)) % mod)
    for i in F:
        RF.append(inv(i))


def comb(x, y):
    return (F[x] * ((RF[x - y] * RF[y]) % mod)) % mod


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

Submission status: Runtime Error

Solution code:
import math

base = 998244353

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

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



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





count = 0

an = 0 

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

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



print(count)

Submission status: Runtime Error

Solution code:
import math

base = 998244353

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

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



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





count = 0

an = 0 

while an <= n:
    if (k - an * a) % b != 0:
        an += 1
        continue
    bn = (k -an * a) // b

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

    an += 1


print(count)

Submission status: Runtime Error

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

def Combi(n,r):
    ANS=1
    for i in range(min(r,n-r)):
        ANS *= (N-i)*INV[i+1]

    return ANS
        

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(N,i)*Combi(N,q)))%mod
        #print(q,r,ANS)

print(ANS)

Submission status: Runtime Error

Solution code:
from math import factorial

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

f = [0]*(N+1)
inv = [0] * (N+1)
f[0] = f[1] = 1

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

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


def nCr(n,r):
    # 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: Runtime Error

Solution code:
import math
def comb(i, j):
    return math.factorial(i) // math.factorial(i-j) // math.factorial(j)
n,a,b,k = map(int,input().split())
ans = 0
for i in range(0,n):
    d = k - a*i
    if d == 0:
        ans += comb(n,i)
        continue
    if d%b == 0 and d > 0:
        ans += comb(n,i) * comb(n,d//b)
    if d<0:
        break
print(ans%998244353)

Submission status: Runtime Error

Solution code:
import math

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

total = 0

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

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

print(int(total) // 998244353)

Submission status: Runtime Error

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

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for r in range(N+1):
    b = (K - A*r) / B
    # 青で塗る箇所が整数ならば
    if b == (K-A*r) // B:
        ans += nCr(N, r) * nCr(N, int(b)) % mod

print(ans % mod)

Submission status: Runtime Error

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

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or n == 0 or r == 0:
        return 0
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for r in range(N+1):
    b = (K - A*r) / B
    # 青で塗る箇所が整数ならば
    if b == (K-A*r) // B and b <= N:
        ans += nCr(N, r) * nCr(N, int(b)) % mod

print(ans)

Submission status: Runtime Error

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

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or n == 0 or r == 0:
        return 0
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for r in range(N+1):
    b = (K - A*r) / B
    # 青で塗る箇所が整数ならば
    if b == (K-A*r) // B:
        ans += nCr(N, r) * nCr(N, int(b)) % mod

print(ans)

Submission status: Runtime Error

Solution code:
import math
n,a,b,k = map(int, input().split())
un = 998244353
def combination(n,r):
    return math.factorial(n)//(math.factorial(r) * math.factorial(n-r))

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

print(str(total % un))

Submission status: Runtime Error

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 (K - a * A) % B == 0:
        b = (K - a * A) // B
        ans += combinations_count(N, a) * combinations_count(N, b)
print(ans % 998244353)

Submission status: Runtime Error

Solution code:
import math

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

l = []
for a in range(N):
    if (K - a * A) % B == 0:
        b = (K - a * A) // B
        l.append((a, b))


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

ans = 0
for pattern in l:
    tmp = 1
    for i in range(2):
        tmp *= combinations_count(N, pattern[i])
    ans += tmp
print(ans % 998244353)

Submission status: Runtime Error

Solution code:
from math import factorial

N,A,B,K = map(int, raw_input().split())
mod=998244353

def product(iterable):
    prod = 1
    for n in iterable:
        prod *= n
    return prod

def npr(n, r):
    return product(range(n - r + 1, n + 1))

def ncr(n, r):
    if r > n // 2:
        r = n - r
    return npr(n, r) // factorial(r)

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

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: Runtime Error

Solution code:
from math import factorial

N,A,B,K = map(int, raw_input().split())
mod=998244353

def product(iterable):
    prod = 1
    for n in iterable:
        prod *= n
    return prod

def npr(n, r):
    return product(range(n - r + 1, n + 1))

def ncr(n, r):
    if r > n // 2:
        r = n - r
    return npr(n, r) // factorial(r)

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

y=None
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: Runtime Error

Solution code:
import math
p = list(map(int,input().split()))
q = max(p[3]//p[1],p[3]//p[2])
al = 0

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

for i in range(q):
  if q == p[3]//p[1]:
    if (p[3] - p[1]*i) % p[2] == 0:
      al += comb(p[0],i)*comb(p[0],(p[3] - p[1]*i) // p[2])
  elif q == p[3]//p[2]:
    if (p[3] - p[2]*i) % p[1] == 0:
      al += comb(p[0],i)*comb(p[0],(p[3] - p[2]*i) // p[1])
print(al)

Submission status: Runtime Error

Solution code:
import math

n, A, B, k = map(int, input().split())

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

res = 0
for a in range(0, n+1):
    if (k - A * a) % B == 0:
        b = (k - A*a) // B
        res += combination(n, a) * combination(n, b) % 998244353
print(res)

Submission status: Runtime Error

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

MOD = 998244353

def comb(n, r):
    if n == 0 or r == 0: return 1
    return ( comb(n, r-1) % MOD) * (n-r+1) / r
    
N,A,B,K = Is()
ans = 0
for x in range(N+1):
    if (K-A*x)/B >= 0 and (K-A*x)/B == int((K-A*x)/B):
        ans += comb(N,x)*comb(N,(K-A*x)/B) % MOD
print(int(ans))

Submission status: Runtime Error

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

sum_p = 0
for a in range(N + 1):
    b = (K - (a * A)) / B
    if int(b) == b:
        sum_p += (combinations_count(N, a) * combinations_count(N, b)) % 998244353
print(sum_p % 998244353)

Submission status: Runtime Error

Solution code:
global MOD,facts,inv
MOD = 998244353

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

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

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

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

Submission status: Runtime Error

Solution code:
global MOD,facts,inv
MOD = 998244353

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

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

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

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