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 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])]
    input_raw = read_func().strip().split()
    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] = power_func(frac_N[i], p - 2, p)

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


if __name__ == '__main__':
    main()

Submission status: 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 (a * modinv(b,sprime) * modinv(c*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:
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])]
    input_raw = read_func().strip().split()
    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] = power_func(frac_N[i], p - 2, p)

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,a,b,k=[int(i) for i in input().split()]
c=a+b
mod=998244353
ans=0

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  #逆元テーブル
inverse = [0, 1]  #逆元テーブル計算用テーブル

for i in range(2,300003):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#以下のcom関数を用いて組み合わせを計算
def com(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

for i in range(n+1):
    if (k-b*i)%a==0 and k-b*i>=0:
        n_a=(k-b*i)//a
        n_b=i
        n_c=min(n_a,n_b)
        n_a, n_b=n_a-min(n_a,n_b), n_b-min(n_a,n_b)
        count=0
        while n_a + n_b + n_c <=n and n_c>=0 and n_b>=0 and n_a>=0:
#            ans+=com(n, n_c, mod) * com(n-n_c, n_b, mod) * com(n-n_c-n_b, n_a, mod) %mod
            if count==0:
                aaa0=com(n, n_c, mod) * com(n-n_c, n_b, mod) * com(n-n_c-n_b, n_a, mod) 
                ans+=aaa0
                count+=1
            n_b+=1
            n_a+=1
            aaa0 = aaa0 * n_c / ( (n_a) * (n_b) * (n-n_c-n_b-n_a) )
            n_c-=1
            if count!=0:
                ans+=aaa

print(ans%mod)

Submission status: Runtime Error

Solution code:
from math import factorial
 
N, A, B, K = map(int, input().split())
ab = []
for a in range(N+1):
  if (K-a*A)%B==0:
    ab.append([a, int((K-a*A)/B)])
to = []
for naka in ab:
  to.append(factorial(N)*factorial(N)//(factorial(naka[0])*factorial(naka[1])*factorial(N-naka[1])*factorial(N-naka[0])))
print(int(sum(to)%998244353))

Submission status: Runtime Error

Solution code:
from math import factorial
 
N, A, B, K = map(int, input().split())
ab = []
for a in range(N):
  if (K-a*A)%B==0:
    ab.append([a, int((K-a*A)/B)])
to = []
for naka in ab:
  to.append(factorial(N)*factorial(N)//(factorial(naka[0])*factorial(naka[1])*factorial(N-naka[1])*factorial(N-naka[0])))
print(int(sum(to)%998244353))

Submission status: Runtime Error

Solution code:
import numpy as np
import math
n,a,b,k = input('input>>').split(' ')

va = np.array([1,0,0])
vb = np.array([0,1,0])
vc = np.array([0,0,1])
v0 = np.array([0,0,0])
def sum_c(sums,pointer,way_vec):
    if sums == k:
        way_vec.append(pointer)
        return way_vec
    if sums > k:
        return way_vec
    sums = sums + c
    pointer = pointer + vc
    sum_c(sums,pointer,way_vec)
def sum_b(sums,pointer,way_vec):
    if sums == k:
        way_vec.append(pointer)
        return way_vec
    if sums > k:
        return way_vec
    sums = sums + b
    pointer = pointer + vb
    sum_b(sums,pointer,way_vec)
    sum_c(sums,pointer,way_vec)
    
def sum_a(sums,pointer,way_vec):
    if sums == k:
        way_vec.append(pointer)
        return way_vec
    if sums > k:
        return way_vec
    sums = sums + a
    pointer = pointer + va
    sum_a(sums,pointer,way_vec)
    sum_b(sums,pointer,way_vec)
    sum_c(sums,pointer,way_vec)

if a > b:
    a,b = b,a
    
if a%2==0 && b%2==0 && k%2==1:
    return 0
else if k<a:
    return 0

wey_vec = []
else if a <= k < b:
    way_vec = sum_a(0,v0,way_vec)
elseif b <= k < c:
    way_vec = sum_a(0,v0,way_vec)
    way_vec = sum_b(0,v0,way_vec)
else if k > c:
    way_vec = sum_a(0,v0,way_vec)
    way_vec = sum_b(0,v0,way_vec)
    way_vec = sum_c(0,v0,way_vec)
else :
    return 0
def comb1(n,r):
    if n==0 or r==0:return 1
    return comb1(n,r-1)*(n-r+1)/r
ans = 0
for i in range(len(way_vec)):
    t= way_vec[i]
    ans = ans + comb1(n,t[0]) * comb1(n-t[0],t[1]) * comb2(n-t[0]-t[1],t[2])
ans = ans % 998244353
return ans

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

ll n,a,b,k;

ll fact[300010];
const ll mod = 998244353;

ll Pow(ll b, ll e){
	if(e<0) e=(-e)*(mod-2)%(mod-1);
	ll ret=1;
	while(e){
		if(e&1) (ret*=b)%=mod;
		(b*=b)%=mod; e>>=1;
	}
	return ret;
}

ll Comb(ll n, ll r){
	return fact[n]*Pow(fact[r], -1)%mod*Pow(fact[n-r], -1)%mod;
}

int main()
{
	read(n,a,b,k);
	fact[0]=1;
	for(int i=1; i<=n; ++i) fact[i]=fact[i-1]*i%mod;
	ll ans = 0;
	for(int p=0; p<=n; ++p){
		ll q = (k-p*a)/b;
		if(p*a + q*b == k){
			(ans += Comb(n, p) * Comb(n, q) % mod) %= mod;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Submission status: Runtime Error

Solution code:
N,A,B,K = list(map(int,input().split()))
r = A
g = A+B
b = B
const = 998244353
ans = 0

def nck(n,k):
    if 0 <= k <= n:
        ret = 1
        for i in range(k):
            ret = ret*(n-i)/(i+1)
        return int(ret)
    return 0

# 混色 r & b
for i in range(min(int(K/r),N+1)):
    num_r = i
    num_b = (K - r*num_r)/b
    cost = num_r + num_b
    if num_b == int(num_b) and cost <= N: # rとbで実現可能 かつ cost <= N
        #if N-num_r >= num_b
        num_r = int(num_r)
        num_b = int(num_b)
        ans += (nck(N,num_r)%const)*(nck(N-num_r,num_b)%const) # r と b のみ
        #print("num_{r,b}",num_r,num_b)
        
        num_g_max = min(num_r,num_b)
        #print("num_g_max",num_g_max)
        
        for j in range(1,num_g_max+1):
            num_g2 = j
            num_r2 = num_r - num_g2
            num_b2 = num_b - num_g2
            #print("num_{r,g,b}",num_r2,num_g2,num_b2)
            #print("nck(N,num_r2)",nck(N,num_r2))
            #print("",)
            ans += (nck(N,num_r2)%const)*(nck(N-num_r2,num_b2)%const)*(nck(N-num_r2-num_b2,num_g2)%const)
        
        """   
        else:
            ans += nck(N,num_b)*nck(N-num_b,num_r)
            num_g2 = min(num_r,num_b)
            num_r2 = num_r - num_g
            num_b2 = num_b - num_g
        """
        
# 単色
if K%r == 0 and K/r<=N and K > 0:
    num_r = int(K/r)
    ans += nck(N,num_r)%const
if K%g == 0 and K/g<=N and K > 0:
    num_g = int(K/g)
    ans += nck(N,num_g)
if K%b == 0 and K/b<=N and K > 0:
    num_b = int(K/b)
    ans += nck(N,num_b)%const
    
if K == 0: print(1)
else: print(ans)

Submission status: Runtime Error

Solution code:
n, A, B, k = map(int, input().split())
count = 0
p =  998244353
import math
def combicount(a, b):
    return math.factorial(a) // (math.factorial(a - b) * math.factorial(b))
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
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
for r in range(0, n):
    for g in range(0, n):
        b =(k-A*r-(A+B)*g)/B
        if b < 0:
            break
        if b == math.floor(b):
            count = count + com(r, g, b)
        else:
            continue
print(count % 998244353)

Submission status: Runtime Error

Solution code:
from math import factorial

N, A, B, K = map(int, input().split())
ab = []
for a in range(min(N, K//A)):
  if (K-a*A)%B==0:
    ab.append([a, int((K-a*A)/B)])
to = []
for naka in ab:
  to.append(factorial(N)*factorial(N)//(factorial(naka[0])*factorial(naka[1])*factorial(N-naka[1])*factorial(N-naka[0])))
print(int(sum(to)%998244353))

Submission status: Runtime Error

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

def my_binom(n,m):
	if n == m:
		return 1
	elif m == 1:
		return n
	elif m > n:
		return 0
	else:
		a = math.factorial(n)
		b = math.factorial(m)
		c = math.factorial(n - m)
		return a // (b*c)

# 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:
import numpy as np
import math

mod = 998244353


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 / math.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 comb(n, x):
    ans = 1
    x = min(x, n-x)
    for i in range(1, x+1):
        ans = (ans * (n - i + 1) // i) % mod
    return int(ans)


# def comb_mult(N, A, B, C):
#     a = int(comb(N, A)) % mod
#     b = int(comb(N-A, B)) % mod
#     c = int(comb(N-A-B, C)) % mod
#     return (a * b * c) % mod


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

    d = math.gcd(math.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 + comb(N, p) * comb(N, q)) % mod

        p += C // A
        if p > N:
            break

    return ans


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

Submission status: Runtime Error

Solution code:
N,A,B,K = list(map(int,input().split()))
r = A
g = A+B
b = B
const = 998244353
ans = 0

def nck(n,k):
    if 0 <= k <= n:
        ret = 1
        for i in range(k):
            ret = ret*(n-i)/(i+1)
        return int(ret)
    return 0

# 混色 r & b
for i in range(1,min(int(K/r),N+1)):
    num_r = i
    num_b = (K - r*num_r)/b
    cost = num_r + num_b
    if num_b == int(num_b) and cost <= N: # rとbで実現可能 かつ cost <= N
        #if N-num_r >= num_b
        num_r = int(num_r)
        num_b = int(num_b)
        ans += (nck(N,num_r)%const)*(nck(N-num_r,num_b)%const) # r と b のみ
        #print("num_{r,b}",num_r,num_b)
        
        num_g_max = min(num_r,num_b)
        #print("num_g_max",num_g_max)
        
        for j in range(1,num_g_max+1):
            num_g2 = j
            num_r2 = num_r - num_g2
            num_b2 = num_b - num_g2
            #print("num_{r,g,b}",num_r2,num_g2,num_b2)
            #print("nck(N,num_r2)",nck(N,num_r2))
            #print("",)
            ans += (nck(N,num_r2)%const)*(nck(N-num_r2,num_b2)%const)*(nck(N-num_r2-num_b2,num_g2)%const)
        
        """   
        else:
            ans += nck(N,num_b)*nck(N-num_b,num_r)
            num_g2 = min(num_r,num_b)
            num_r2 = num_r - num_g
            num_b2 = num_b - num_g
        """
        
# 単色
if K%r == 0 and K/r<=N and K > 0:
    num_r = int(K/r)
    ans += nck(N,num_r)%const
if K%g == 0 and K/g<=N and K > 0:
    num_g = int(K/g)
    ans += nck(N,num_g)
if K%b == 0 and K/b<=N and K > 0:
    num_b = int(K/b)
    ans += nck(N,num_b)%const
    
if K == 0: print(1)
else: print(ans)

Submission status: Runtime Error

Solution code:
n, A, B, k = map(int, input().split())
count = 0
import math
def combicount(a, b):
    return math.factorial(a) // (math.factorial(a - b) * math.factorial(b))
def com(r, g, b):
    return combicount(n, r)*combicount(n-r, g)*combicount(n-r-g, b)
for g in range(0, n):
    for r in range(0, n):
        b =(k-A*r-(A+B)*g)/B
        if b < 0:
            break
        if b == math.floor(b):
            count = count + com(r, g, b)
        else:
            continue
print(count % 998244353)

Submission status: Runtime Error

Solution code:
import math
def divide(A,B,C,D,E):
  F = [B,C,D,E]
  F.sort()
  tail = F[-1]
  F = F[:-1]
  G = 1
  for i in range(A-tail):
    G *= A - i
  for f in F:
    G /= f
  return G
N,A,B,K = map(int, input().split())
count = 0
Nf = math.factorial(N)
P = []
c = 0
while c < N:
  if K % B == 0:
    if K//B <= N:
      print((c, K//B))
      P.append([c, K//B])
  K -= A
  c += 1
for p in P:
  for G in range(min(p[0],p[1]) + 1):
    W = N - p[0] - p[1] + G
    if W >= 0:
      #divider = math.factorial(p[0]-G) * math.factorial(p[1]-G) * math.factorial(G) * math.factorial(W)
      pattern = divide(Nf, math.factorial(p[0]-G), math.factorial(p[1]-G), math.factorial(G), math.factorial(W))
      count += pattern
count *= 10 ** k
if count > 998244353:
  count = count % 998244353
print(count)

Submission status: Runtime Error

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


thisMap = {}
def search(N,K):
    global A, B
    plus = 0
    if N == 1:
        if K == 0 or K == A or K == B or K == A+B:
            return 1
        else:
            return 0

    plus += search(N-1,K)
    if K-A >= 0:
        if str(N-1) + '-' + str(K-A) in thisMap.keys():
            plus += thisMap[str(N-1) + '-' + str(K-A)]
        else:
            plus += search(N-1, K-A)
    if K-B >= 0:
        if str(N-1) + '-' + str(K-B) in thisMap.keys():
            plus += thisMap[str(N-1) + '-' + str(K-B)]
        else:
            plus += search(N-1, K-B)
    if K-A-B >= 0:
        if str(N-1) + '-' + str(K-A-B) in thisMap.keys():
            plus += thisMap[str(N-1) + '-' + str(K-A-B)]
        else:
            plus += search(N-1, K-A-B)
    return plus
# map = [[0 for _ in range(N)] for _ in range(K+1)]

# for i in range(N):
#     map[0][i] = 1
#
# for i in range(1,K+1):
#     if i == A or i == B or i == A+B:
#         map[i][0] = 1
# print("HI")

# for i in range(1,K+1):
#     for j in range(1,N):
#         plus = 0
#         plus += map[i][j-1]
#         if i - A >= 0:
#             plus += map[i-A][j-1]
#         if i - (A+B) >= 0:
#             plus += map[i-A-B][j-1]
#         if i - B >= 0:
#             plus += map[i-B][j-1]
#         map[i][j] = plus
# for i in range(1,6 * (10 ** 2)):
#     if N > i * 500:
#         search(i * 500, K)

print(search(N,K))

Submission status: Runtime Error

Solution code:
input = input().split(" ")
n = int(input[0])
a = int(input[1])
b = int(input[2])
k = int(input[3])

import math

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

def func(n, a, b, k):
    if k < a and k < b:
        print(1)
        return
    combination = []
    temp = k
    num_a = 0
    while temp >= num_a:
        num_b = (temp-num_a)/b
        
        if num_b%1 == 0:
            combination.append([int(num_a/a), int(num_b)])
        num_a += a

    color_combi = []
    for c in combination:
        max_num = min(c[0]+1, n)
        for num_red in range(0,c[0]+1):
            num_green = c[0]-num_red
            num_blue = c[1]-num_green
            if num_red >= 0 and num_green >= 0 and num_blue >= 0:  
                if num_red + num_blue + num_green <= n:
                    color_combi.append([num_red, num_green, num_blue])
    result = 0

    for c in color_combi:
        result += comb(n, c[0])*comb(n-c[0],c[1])*comb(n-c[0]-c[1], c[2])
        
    print(result)
    
func(n,a,b,k)

Submission status: Runtime Error

Solution code:
import itertools
import math

N,A,B,K = (int(i) for i in input().split())

'''
赤色:A点
緑色:A+B点
青色:B点

合計ちょうどKになるような組み合わせの数は？
'''

maxA = K//A
maxB = K//B
kumiawase = 0
narabi = 0

if K == 0:
    print(1)
else:
    for i in range(1,maxA+1):
        for j in range(1,maxB+1):
            if(K%(i*A+j*B)==0):
                for k in range(min(i,j)+1):
                    #個数
                    aka = math.factorial(i-k)
                    ao = math.factorial(j-k)
                    midori = math.factorial(k)
                    shiro = math.factorial(N-(i-k+j-k+k))

                    narabi += math.factorial(N)/(aka*ao*midori*shiro)

    print(int(narabi%998244353))

Submission status: Runtime Error

Solution code:
import itertools
import math

N,A,B,K = (int(i) for i in input().split())

'''
赤色:A点
緑色:A+B点
青色:B点

合計ちょうどKになるような組み合わせの数は？
'''

maxA = K//A
maxB = K//B
kumiawase = 0
narabi = 0

if K == 0:
    print(1)
else:
    for i in range(1,maxA+1):
        for j in range(1,maxB+1):
            if(K%(i*A+j*B)==0):
                kumiawase += 1
                kumiawase += min(i,j)
                for k in range(min(i,j)+1):
                    #個数
                    aka = math.factorial(i-k)
                    ao = math.factorial(j-k)
                    midori = math.factorial(k)
                    shiro = math.factorial(N-(i-k+j-k+k))
                    narabi += math.factorial(N)/(aka*ao*midori*shiro)
                    print(int(narabi%998244353))
                
    print(kumiawase)
    print(int(narabi%998244353))

Submission status: Runtime Error

Solution code:
input = input().split(" ")
n = int(input[0])
a = int(input[1])
b = int(input[2])
k = int(input[3])

import math

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

def func(n, a, b, k):
    if k < a and k < b:
        print(1)
        return
    combination = []
    temp = k
    num_a = 0
    while temp > num_a:
        num_b = (temp-num_a)/b
        
        if num_b%1 == 0:
            combination.append([int(num_a/a), int(num_b)])
        num_a += a

    color_combi = []
    for c in combination:
        max_num = min(c[0]+1, n)
        for num_red in range(0,c[0]+1):
            num_green = c[0]-num_red
            num_blue = c[1]-num_green
            if num_red >= 0 and num_green >= 0 and num_blue >= 0:  
                if num_red + num_blue + num_green <= n:
                    color_combi.append([num_red, num_green, num_blue])
    result = 0

    for c in color_combi:
        result += comb(n, c[0])*comb(n-c[0],c[1])*comb(n-c[0]-c[1], c[2])
        
    print(result)
    
        

func(n,a,b,k)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

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

memo={}
memo[(0,0)]=1
memo[(1,A)]=1
memo[(1,B)]=1
memo[(1,A+B)]=1



def func(i,k):
	if (i,k) in memo:
		return memo[(i,k)]
	if i<=0 or k<0: return 0
	#print i-1, k-A,i-1,k-B,i-1, k-(A+B),i-1,k
	result=func(i-1, k-A)%mod+func(i-1, k-B)%mod+func(i-1, k-(A+B))%mod+func(i-1,k)%mod
	result=result%mod

	memo[(i,k)]=result
	return result


print func(N,K)

Submission status: Runtime Error

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

mod = 998244353 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
N1=10**4+1
for i in range( 2, N1 + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
li = input().split()
N=int(li[0])
A=int(li[1])
B=int(li[2])
K=int(li[3])
count=0
for i in range (N+1):
    for k in range(N+1):
        if((A+B)*N-A*i-B*k==K):
            
            ca=cmb(N, i,mod)
            cb=cmb(N,k,mod)
            count=count+ca*cb
print(count%mod)

Submission status: Runtime Error

Solution code:
import math
mod = 998244353
N, A, B, K = map(long, raw_input().split())
if K == 0:
  print 1
else:
  ans = 0
  Gmax = K / (A+B)
  N_RB_Gmax = N -Gmax
  K_RB_Gmax = K - (A+B)*Gmax
  kouho_Gmax = []
  for R_Gmax in range((N_RB_Gmax-K_RB_Gmax)/(B-A)+2):
    B_Gmax = (K_RB_Gmax-A*R_Gmax)/B
    if A*R_Gmax+(A+B)*Gmax+B*B_Gmax == K and R_Gmax+Gmax+B_Gmax<= N and R_Gmax>=0 and B_Gmax >= 0:
      kouho_Gmax.append((R_Gmax, B_Gmax))
      ans += (math.factorial(N)/math.factorial(R_Gmax)/math.factorial(Gmax)/math.factorial(B_Gmax)/math.factorial(N-R_Gmax-Gmax-B_Gmax))%mod
  for G in range(Gmax)[::-1]:
    isEnd = True
    for k in kouho_Gmax:
      R = k[0]+(Gmax-G)
      B = k[1]+(Gmax-G)
      if R+G+B <= N:
        isEnd = False
        ans += (math.factorial(N)/math.factorial(R)/math.factorial(G)/math.factorial(B)/math.factorial(N-R-G-B))%mod
    if isEnd:
      break
  print ans

Submission status: Runtime Error

Solution code:
l = input()

Submission status: Runtime Error

Solution code:
from scipy.special import perm, comb

def C(x,y,dic,com):
    if y==0 or x == y:
        return 1
    elif (x,y) in dic.keys():
        return dic[(x,y)]
    else:
        dic[(x,y)] = comb(x,y,exact=True)#(C(x-1,y-1,dic,com)+C(x-1,y,dic,com))
        return dic[(x,y)]

def main():
    MAX =  998244353
    n = list(map(int,input().split()))
    N = n[0]
    A = n[1]
    B = n[2]
    K = n[3]

    r = A
    g = A+B
    b = B

    point = []

    X = -1
    while(K - X * r > -1 ):
        X = X + 1
        if ((K-X * r) % (b)):
            continue
        else:
            point.append((X,int((K-X * r) / (b))))
            continue
    dic2 = []
    for i in point:
        x = i[0]
        y = 0
        z = i[1]
        while((x > -1)and(z > -1)):
            if (x + y + z) > N:
                pass
            else:
                dic2.append([x+y+z,x,y,z])
            x = x -1
            z = z -1
            y = y +1
    dic2.sort()
    print(dic2)
    count = 0
    dict = {}

    for i in dic2:
        x = i[1]
        y = i[2]
        z = i[3]
        count = (count + C(N,x,dict,comb)*C(N-x,y,dict,comb)*C(N-(x+y),z,dict,comb))%MAX
        
    print(count)
main()

Submission status: Runtime Error

Solution code:
n,a,b,k=[int(i) for i in input().split()]
c=a+b
mod=998244353
ans=0

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  #逆元テーブル
inverse = [0, 1]  #逆元テーブル計算用テーブル

for i in range(2,300000):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#以下のcom関数を用いて組み合わせを計算
def com(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

#test=2*3*com(4, 2, mod) + com(4,3,mod)
#print(test)

for i in range(n+1):
    if (k-b*i)%a==0 and k-b*i>=0:
        n_a=(k-b*i)//a
        n_b=i
#        print(n_a, n_b)
        
        n_c=min(n_a,n_b)
        n_a, n_b=n_a-min(n_a,n_b), n_b-min(n_a,n_b)
#        print(n_a, n_b, n_c)

        while n_a + n_b + n_c <=n and n_c>=0 and n_b>=0 and n_a>=0:
            ans+=com(n, n_c, mod) * com(n-n_c, n_b, mod) * com(n-n_c-n_b, n_a, mod)
            n_c-=1
            n_b+=1
            n_a+=1
print(ans%mod)

Submission status: Runtime Error

Solution code:
import numpy as np
import scipy.misc as scm
import math

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

N=int(N)
A=int(A)
B=int(B)
K=int(K)

a=np.arange(2*N+1)
b=np.arange(2*N+1)

a_score=a*A
b_score=b*B

arr=[]
for i in range(2*N+1):
	if ((K-a_score[i])%B==0) and (K-a_score[i]>=0):
		arr.append([i,int((K-a_score[i])/B)])

arr=np.array(arr)

arr1=[]
for i in range(np.shape(arr)[0]):
	for j in range(N):
		if (arr[i][0]-j<N)and(arr[i][0]-j>=0)and(arr[i][1]-j<N)and(arr[i][1]-j>=0):
			arr1.append([arr[i][0]-j,arr[i][1]-j,j])
	
arr1=np.array(arr1)

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

arr2=np.zeros(np.shape(arr1))
num=0
for i in range(np.shape(arr1)[0]):
	num1=1
	n=0
	for j in range(np.shape(arr1)[1]):
		arr2[i][j]=math.factorial(arr1[i][j])
	num1=permutations_count(N,np.sum(arr1[i]))/np.prod(arr2[i])
	num=num+num1

print(int(num)%998244353)

Submission status: Runtime Error

Solution code:
import numpy as np
import scipy.misc as scm
import math

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

N=int(N)
A=int(A)
B=int(B)
K=int(K)

a=np.arange(2*N+1)
b=np.arange(2*N+1)

a_score=a*A
b_score=b*B

arr=[]
for i in range(2*N+1):
	if ((K-a_score[i])%B==0) and (K-a_score[i]>=0):
		arr.append([i,int((K-a_score[i])/B)])

arr=np.array(arr)

arr1=[]
for i in range(np.shape(arr)[0]):
	for j in range(N):
		if (arr[i][0]-j<N)and(arr[i][0]-j>=0)and(arr[i][1]-j<N)and(arr[i][1]-j>=0):
			arr1.append([arr[i][0]-j,arr[i][1]-j,j])
	
arr1=np.array(arr1)

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

arr2=np.zeros(np.shape(arr1))
num=0
for i in range(np.shape(arr1)[0]):
	num1=1
	n=0
	for j in range(np.shape(arr1)[1]):
		arr2[i][j]=math.factorial(arr1[i][j])
	num1=permutations_count(N,np.sum(arr1[i]))/np.prod(arr2[i])
	num=num+num1

print(int(num)%998244353)

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
from scipy.special import comb

N = int(input())
A = int(input())
B = int(input())
K = int(input())
a=0
for i in range(int(N/A)):
    c = comb(N,i,exact=True)
    N = N - A*i
    a = a + sum(comb(N,j,exact=True) for j in range(int(N/B)))

print(a%998244353)