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:
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 += (nCr(N,i) * nCr(N,f)) % MOD
        
print(ans)

Submission status: Runtime Error

Solution code:
#from scipy.misc import comb
n, a, b, k = map(int,input().split())	
#n, a, b, k = 90081, 33447, 90629, 6391049189
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)
    ret += (comb(n,na,1) * comb(n,nb,1)) % modN

print(ret)

Submission status: Runtime Error

Solution code:
#from scipy.misc import comb
n, a, b, k = map(int,input().split())	
modN = 998244353
 
def prepare(n, MOD): 
  # n! の計算
  fn = [1] * (n + 1)
  f = 1
  for m in range(1, n + 1):
    f *= m
    f %= MOD
    fn[m] = f
    
  # n!^-1 の計算
  inv = pow(f, MOD - 2, MOD)
  # n!^-1 - 1!^-1 の計算
  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 = prepare(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)
    ret += (comb(n,na,1) * comb(n,nb,1)) % modN
 
print(ret)

Submission status: Runtime Error

Solution code:
#from scipy.misc import comb
n, a, b, k = map(int,input().split())	
modN = 998244353
 
def prepare(n, MOD): 
  # n! の計算
  fn = [1] * (n + 1)
  f = 1
  for m in range(1, n + 1):
    f *= m
    f %= MOD
  fn[n] = f
    
  # n!^-1 の計算
  inv = pow(f, MOD - 2, MOD)
  # n!^-1 - 1!^-1 の計算
  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 = prepare(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)
    ret += (comb(n,na,1) * comb(n,nb,1)) % modN
 
print(ret)

Submission status: Runtime Error

Solution code:
from scipy.misc import comb
n, a, b, k = map(int,input().split())	
modN = 998244353
 
def prepare(n, MOD): 
  # n! の計算
  fn = [1] * (n + 1)
  f = 1
  for m in range(1, n + 1):
    f *= m
    f %= MOD
  fn[n] = f
    
  # n!^-1 の計算
  inv = pow(f, MOD - 2, MOD)
  # n!^-1 - 1!^-1 の計算
  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 = prepare(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)
    ret += (comb(n,na,1) * comb(n,nb,1)) % modN
 
print(ret)

Submission status: Runtime Error

Solution code:
import math
def combination(n, r):
    n = n % 998244353
    r = r % 998244353
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
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 += combination(n, i) * combination(n, q) % 998244353

print(ans)

Submission status: Runtime Error

Solution code:
import math
def combination(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
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 += combination(n, i) * combination(n, q) % 998244353

print(ans)

Submission status: Runtime Error

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:
        j //= B
        n+=(memo[i]*memo[j])%998244353
        n%=998244353
print(n%998244353)

Submission status: Runtime Error

Solution code:
N,A,B,K = map(int,input().split(" "))
mod = 998244353
ncr = [1]*(N+1)
v = 1
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):
	if (K - (a * A)) % B == 0:
		pat += ncr[a]*ncr[(K - (a * A))//B]
		pat %= mod

print(pat % mod)

Submission status: Runtime Error

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

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

for i in range(N+1):
    j = K-A*i
    if j < 0:
        break
    if (K-A*i)%B==0:
        j //= B
        n+=(memo[i]*memo[j])%998244353
        n%=998244353
print(n%998244353)

Submission status: Runtime Error

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

def gcd(a,b):
	return a if b == 0 else gcd(b,a%b)
v = 1
for i in range(N):
	v = (v * ((N-i)%mod) * pow((i+1),mod-2,mod)) % mod
	ncr[i+1] = v%mod

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

A //= g
B //= g
K //= g
pat = 0
for a in range(N):
	if (K - (a * A)) % B == 0:
		pat += ncr[a]*ncr[(K - (a * A))//B]
		pat %= mod

print(pat % mod)

Submission status: Runtime Error

Solution code:
import math
N,A,B,K = map(int,input().split(" "))
mod = 998244353
ncr = [1]*(N+1)
v = 1
for i in range(N):
	v = (v * ((N-i)%mod) * pow((i+1),mod-2,mod)) % mod
	ncr[i+1] = v%mod

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

A //= g
B //= g
K //= g
pat = 0
for a in range(N):
	if (K - (a * A)) % B == 0:
		pat += ncr[a]*ncr[(K - (a * A))//B]
		pat %= mod

print(pat % mod)

Submission status: Runtime Error

Solution code:
import math
N,A,B,K = map(int,input().split(" "))
mod = 998244353
ncr = [1]*(N+1)
v = 1
for i in range(N):
	v = (v * (N-i)//(i+1))
	ncr[i+1] = v%mod																															


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

A //= g
B //= g
K //= g
pat = 0
for a in range(N):
	if (K - (a * A)) % B == 0:
		pat += ncr[a]*ncr[(K - (a * A))//B]
		pat %= mod

print(pat % mod)

Submission status: Runtime Error

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

def prepare(n, MOD): 
    # n! の計算
    fn = [1] * (n + 1)
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn[n] = f
     
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    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 = prepare(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)
    ret += (comb(n,na,1) * comb(n,nb,1)) % modN

print(ret)

Submission status: Runtime Error

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

def prepare(n, MOD): 
    # n! の計算
    fn = [1] * (n + 1)
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn[n] = f
     
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    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 = prepare(n, modN)

def comb(n,k,f):
  # f is not used
  return fn[n] * invs[k] * 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)
    ret += (comb(n,na,1) * comb(n,nb,1)) % modN

print(ret)

Submission status: Runtime Error

Solution code:
from math import gcd
N,A,B,K = map(int,input().split(" "))
mod = 998244353
def nCr(n,r):
	r = min(n,n-r)
	up,lw = 1,1
	for i in range(r):
		up *= (n-i)
		lw *= (r-i)
	return (up // lw)%mod

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

A //= g
B //= g
K //= g
pat = 0
for a in range(N):
	if (K - (a * A)) % B == 0:
		pat += nCr(N,a)*nCr(N,(K - (a * A))//B)
		pat %= mod

print(pat % mod)

Submission status: Runtime Error

Solution code:
n, a, b, k = [int(i) for i in input().split()]
p = 998244353

def fact(n, p):
    n_ = 1
    yield n_
    for i in range(1, n+1):
         n_ = (n_*i) % p
         yield n_

def invfact(n, f, p):
    m = pow(f[n], p-2, p)
    yield m
    for i in range(n, 0, -1):
        m = m * i % p
        yield m

f = list(fact(n+1, p))
rf = list(invfact(n+1, f, p))
rf.reverse()
ans = 0

for x in range(n+1):
    y = (k-x*a)/b
    if not y.is_integer() or y > n:
        continue
    y = int(y)

    ans += (f[n] * rf[x] % p * rf[n-x] % p) * (f[n] * rf[y] % p * rf[n-y] % p) % p

print(ans%p)

Submission status: Runtime Error

Solution code:
n, a, b, k = [int(i) for i in input().split()]
p = 998244353

def fact(n, p):
    n_ = 1
    yield n_
    for i in range(1, n+1):
         n_ = (n_*i) % p
         yield n_

def invfact(n, f, p):
    m = pow(f[n], p-2, p)
    yield m
    for i in range(n, 0, -1):
        m = m * i % p
        yield m

f = list(fact(n+1, p))
rf = list(invfact(n+1, f, p))
rf.reverse()
ans = 0

for x in range(n+1):
    y = (k-x*a)/b
    if not y.is_integer():
        continue
    y = int(y)

    ans += (f[n] * rf[x] % p * rf[n-x] % p) * (f[n] * rf[y] % p * rf[n-y] % p) % p

print(ans%p)

Submission status: Runtime Error

Solution code:
n, a, b, k = [int(i) for i in input().split()]
p = 998244353

def fact(n, p):
    n_ = 1
    yield n_
    for i in range(1, n+1):
         n_ = (n_*i) % p
         yield n_

def invfact(n, f, p):
    m = pow(f[n], p-2, p)
    yield m
    for i in range(n, 0, -1):
        m = m * i % p
        yield m

f = list(fact(n, p))
rf = list(invfact(n, f, p))
rf.reverse()
ans = 0

for x in range(n+1):
    y = (k-x*a)/b
    if not y.is_integer():
        continue
    y = int(y)

    ans += (f[n] * rf[x] % p * rf[n-x] % p) * (f[n] * rf[y] % p * rf[n-y] % p) % p

print(ans%p)

Submission status: Runtime Error

Solution code:
import numpy as np

mod = 998244353


def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)


def ii():
    return int(input())


def lii():
    return list(map(int, input().split(' ')))


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


def lcm(a, b):
    """
    最小公倍数
    """
    return a * b / gcd(a,b)


# def main_old():
#     N, A, B, K = lii()
#     dp = np.zeros([N+1, K+1])
#     dp[:, 0] = 1
#     for n in range(1, N+1):
#         for k in range(K+1):
#             c = dp[n-1][k]
#             if k - A >= 0: c += dp[n-1][k-A]
#             if k - B >= 0: c += dp[n-1][k-B]
#             if k - (A+B) >= 0: c += dp[n-1][k-(A+B)]
#             dp[n][k] = c
#
#     print(int(dp[N][K]) % mod)


def solve_eucl(A, B, K, N):
    for _x in range(N):
        if (K - A * _x) % B == 0:
            x = _x
            y = (K - A * _x) // B
            return x, y


def modinv(a, m):
    orgm = m
    x, lastx, y, lasty = 0, 1, 1, 0
    while m:
        a, (quotient, m) = m, divmod(a, m)
        x, lastx = lastx - quotient * x, x
        y, lasty = lasty - quotient * y, y
    if a != 1:
        raise ValueError
    return lastx % orgm


def fastcombmod(m, n):
    nn = min(n, m - n)
    num = 1
    div = 1
    for i in range(nn):
        num *= m - i
        if num > mod:
            num %= mod
        div *= i + 1
        if div > mod:
            div %= mod
    return (num * modinv(div, mod)) % mod


def combmod_table(m):
    num = 1
    div = 1
    t = [1]
    for i in range(m // 2 ):
        num *= m - i
        if num > mod:
            num %= mod
        div *= i + 1
        if div > mod:
            div %= mod

        t.append((num * modinv(div, mod)) % mod)

    return t


def main():
    N, A, B, K = lii()
    if K == 0: return 1

    d = gcd(gcd(A, B), K)
    if d > 1:
        A = A // d
        B = B // d
        K = K // d

    # x, y = solve_eucl(A, B, K, N)
    #
    # C = int(lcm(A, B))
    # ans = 0
    # p = x
    # while True:
    #     q = (K - A * p) // B
    #     if q <= 0:
    #         break
    #
    #     ans = (ans + fastcombmod(N, p) * fastcombmod(N, q)) % mod
    #     p += C // A
    #     if p > N:
    #         break
    #
    # return ans
    ans = 0
    ct = combmod_table(N)
    for x in range(N+1):
        if (K - A * x) % B == 0:
            y = (K - A * x) // B
            ans = ans + ct[min(x, N-x)] * ct[min(y, N-y)]
            ans = ans % mod
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

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

comb_mem = [1]
acc = 1
for i in range(1, n + 1):
  acc = acc * (n + 1 - i) // i
  comb_mem.append(acc)
ans = 0
for na in range(n + 1):
  if not (k - a * na) % b:
    nb = (k - a * na) // b
    print(na, nb)
    ans += comb_mem[na] * comb_mem[nb]
    ans %= 998244353
print(ans)

Submission status: Runtime Error

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])]
    cnt = 0
    li = []
    for t in range(N + 1):
        if (K - t * A)%B == 0:
            u = (K - t * A)/B
            if t >= 0 and u >= 0:
                li.append((t, u))


    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] = -1

    s = 0L
    for i in range(len(li)):
        t = li[i][0]
        u = li[i][1]
        if power_N[t] == -1:
            power_N[t] = power_func(frac_N[t], p - 2, p)
        if power_N[N - t] == -1:
            power_N[N - t] = power_func(frac_N[N - t], p - 2, p)
        if power_N[u] == -1:
            power_N[u] = power_func(frac_N[u], p - 2, p)
        if power_N[N - u] == -1:
            power_N[N - u] = power_func(frac_N[N - u], p - 2, p)

        s = (s + ((frac_N[N] * power_N[t] * power_N[N - t]) % p) * ((frac_N[N] * power_N[u] * power_N[N - u]) % p)) % p
    print s



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
mod=998244353
N,A,B,K=map(int,input().split())
 
#繰り返し二乗法
def great_power(x, y):
    if   y == 0:
      return 1
    elif y == 1:
      return x % mod
    elif y % 2 == 0:
      return great_power(x, y//2)**2 % mod
    else:
      return great_power(x, y//2)**2 * x % mod

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

#逆元計算
inverse=[0]*(N+1)
inverse[N] = great_power(factorial[N], mod-2)
for i in range(N-1, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod

#combination計算
def nCr(n,r):
  if n==r or n<r:
    return 1
  return factorial[n] * inverse[r] * inverse[n-r] % mod

ans=0
for i in range(N+1):
  if (K-A*i)%B==0 and (K-A*i)//B <= N:
    ans+=(nCr(N,i) * nCr(N,(K-A*i)//B))
    ans%=mod

print(ans)

Submission status: Runtime Error

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])]
    cnt = 0
    li = []
    for t in range(N + 1):
        if (K - t * A)%B == 0:
            u = (K - t * A)/B
            if t >= 0 and u >= 0:
                li.append((t, u))


    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] = -1

    s = 0L
    for i in range(len(li)):
        t = li[i][0]
        u = li[i][1]
        if power_N[t] == -1:
            power_N[t] = power_func(frac_N[t], p - 2, p)
        if power_N[N - t] == -1:
            power_N[N - t] = power_func(frac_N[N - t], p - 2, p)
        if power_N[u] == -1:
            power_N[u] = power_func(frac_N[u], p - 2, p)
        if power_N[N - u] == -1:
            power_N[N - u] = power_func(frac_N[N - u], p - 2, p)

        s = (s + ((frac_N[N] * power_N[t] * power_N[N - t]) % p) * ((frac_N[N] * power_N[u] * power_N[N - u]) % p)) % p
    print s
##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])]
##    cnt = 0
##    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] = -1
##
##    s = 0L
##    for i in range(len(li)):
##        w = li[i][0]
##        x = li[i][1]
##        y = li[i][2]
##        z = li[i][3]
##        if power_N[x] == -1:
##            power_N[x] = power_func(frac_N[x], p - 2, p)
##        if power_N[y] == -1:
##            power_N[y] = power_func(frac_N[y], p - 2, p)
##        if power_N[z] == -1:
##            power_N[z] = power_func(frac_N[z], p - 2, p)
##        if power_N[w] == -1:
##            power_N[w] = power_func(frac_N[w], p - 2, p)
##        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: Runtime Error

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

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
		sum += (memo[i] * memo[j]) % sprime

print(sum)

Submission status: Runtime Error

Solution code:
N,A,B,K=map(int,input().split())
mod = 998244353
#x!のmodP逆元を求めるx^-1=x^(p-2)
table=[1]
a=1
for i in range(1,N+1):
    a=(a*pow(i,mod-2,mod))%mod
    table.append(a)

num=1
for i in range(1,N+1):
    num = (num*i) %mod


number =0
for i in range(N):
    if (K-A*i)%B==0 and K-A*i>=0:
        j=(K-A*i)//B
        t = (num*num)%mod
        t = (t*table[i])%mod
        t = (t*table[j])%mod
        t = (t*table[N-i])%mod
        t = (t*table[N-j])%mod
        number = (number+t)%mod
print(number)

Submission status: Runtime Error

Solution code:
mod=998244353
N,A,B,K=map(int,input().split())
 
#繰り返し二乗法
def great_power(x, y):
    if   y == 0:
      return 1
    elif y == 1:
      return x % mod
    elif y % 2 == 0:
      return great_power(x, y//2)**2 % mod
    else:
      return great_power(x, y//2)**2 * x % mod

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

#逆元計算
inverse=[0]*(N+1)
inverse[N] = great_power(factorial[N], mod-2)
for i in range(N-1, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod

#combination計算
def nCr(n,r):
  if n==r or n<r:
    return 1
  return factorial[n] * inverse[r] * inverse[n-r] % mod

ans=[]
for i in range(N+1):
  if (K-A*i)%B==0 and (K-A*i)//B <= N:
    ans.append((i,(K-A*i)//B))

out=0
for x,y in ans:
  out+=(nCr(N,x)*nCr(N,y))%mod
print(out%mod)

Submission status: Runtime Error

Solution code:
from fractions import gcd
import sys
sys.setrecursionlimit(10**7) 

N,A,B,K=map(int,input().split())
mod = 998244353
#x!のmodP逆元を求めるx^-1=x^(p-2)
table=[1]
a=1
for i in range(1,N+1):
    a=(a*pow(i,mod-2,mod))%mod
    table.append(a)

num=1
for i in range(1,N+1):
    num = (num*i) %mod


number =0
for i in range(N):
    if (K-A*i)%B==0 and K-A*i>=0:
        j=(K-A*i)//B
        t = (num*num)%mod
        t = (t*table[i])%mod
        t = (t*table[j])%mod
        t = (t*table[N-i])%mod
        t = (t*table[N-j])%mod
        number = (number+t)%mod
print(number)

Submission status: Runtime Error

Solution code:
from fractions import gcd
import sys
sys.setrecursionlimit(10**7) 

N,A,B,K=map(int,input().split())
mod = 998244353
#x!のmodP逆元を求めるx^-1=x^(p-2)
table=[1]
a=1
for i in range(1,N+1):
    a=(a*pow(i,mod-2,mod))%mod
    table.append(a)

num=1
for i in range(1,N+1):
    num = (num*i) %mod


number =0
for i in range(N):
    if (K-A*i)%B==0:
        j=(K-A*i)//B
        t = (num*num)%mod
        t = (t*table[i])%mod
        t = (t*table[j])%mod
        t = (t*table[N-i])%mod
        t = (t*table[N-j])%mod
        number = (number+t)%mod
print(number)

Submission status: Runtime Error

Solution code:
mod=998244353
N,A,B,K=map(int,input().split())
 
#繰り返し二乗法
def great_power(x, y):
    if   y == 0:
      return 1
    elif y == 1:
      return x % mod
    elif y % 2 == 0:
      return great_power(x, y//2)**2 % mod
    else:
      return great_power(x, y//2)**2 * x % mod

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

#逆元計算
inverse=[0]*(N+1)
inverse[N] = great_power(factorial[N], mod-2)
for i in range(N-1, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod

#combination計算
def nCr(n,r):
  if n==r or n<r:
    return 1
  return factorial[n] * inverse[r] * inverse[n-r] % mod

ans=[]
for i in range(N+1):
  if (K-A*i)%B==0:
    ans.append((i,(K-A*i)//B))

out=0
for x,y in ans:
  out+=(nCr(N,x)*nCr(N,y))%mod
print(out%mod)

Submission status: Runtime Error

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):
  """a^b mod 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])]
    cnt = 0
    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] = -1

    s = 0L
    for i in range(len(li)):
        w = li[i][0]
        x = li[i][1]
        y = li[i][2]
        z = li[i][3]
        if power_N[x] == -1:
            power_N[x] = power_func(frac_N[x], p - 2, p)
        if power_N[y] == -1:
            power_N[y] = power_func(frac_N[y], p - 2, p)
        if power_N[z] == -1:
            power_N[z] = power_func(frac_N[z], p - 2, p)
        if power_N[w] == -1:
            power_N[w] = power_func(frac_N[w], p - 2, p)
        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: Runtime Error

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(N,i) * binom(N,j)) % sp

print(sum)

Submission status: Runtime Error

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

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(N,i) * binom(N,j)) % sp

print(sum)