Problem:


Score : 700 points

Problem Statement

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

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

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

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

Constraints

1 ≤ N ≤ 3×10^5

1 ≤ A,B ≤ 3×10^5

0 ≤ K ≤ 18×10^{10}

All values in the input are integers.

Input

Input is given from Standard Input in the following format:

N A B K

Output

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

Sample Input 1

4 1 2 5

Sample Output 1

40

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

1 green, 1 blue

1 red, 2 blues

2 reds, 1 green

3 reds, 1 blue

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

Sample Input 2

2 5 6 0

Sample Output 2

1

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

Sample Input 3

90081 33447 90629 6391049189

Sample Output 3

577742975



Sample input:
4 1 2 5


Sample output:
40

Submission status: Accepted

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

def cmb(n, r):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return f_table[n] * inverse_table[r] * inverse_table[n-r] % mod


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

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

Submission status: Accepted

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 and 0 <= b <= N:
        ans += nCr(N, r) * nCr(N, int(b)) % mod

print(ans % mod)

Submission status: Accepted

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

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

P = 998244353

N, A, B, K = reads()

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):
  # assert 0 <= k <= n
  return fact[n] * invfact[k] * invfact[n-k] % P

result = 0
for x in range(N+1):
  y, r = divmod(K - A * x, B)
  if r == 0 and 0 <= y <= N:
    result = result + comb(N, x) * comb(N, y) % P

print(result % P)

Submission status: Accepted

Solution code:
import math
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):
    global f, inv
    return (f[n] * inv[r]) % un * inv[n-r] % un

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

print(str(total % un))

Submission status: Accepted

Solution code:
import sys,collections,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
mod = 998244353 #出力の制限
N = 3*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N,A,B,K = Is()
ans = 0
for x in range(N+1):
    y = (K-A*x)/B
    if 0 <= y <= N and y.is_integer():
        ans += cmb(N,x,mod)*cmb(N,int(y),mod) % mod
print(ans % mod)

Submission status: Accepted

Solution code:
import math

N, A, B, K = map(int, input().split())
mod = 998244353
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]


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


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

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

Submission status: Accepted

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

# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
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)

# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

# 組み合わせを全部メモ化
C = [0]*(N+1)
C[0] = C[N] = 1
for k in range(1,N//2+1):
    v = C[k-1]*(N-k+1)*modinv(k,MOD)
    v %= MOD
    C[k] = C[N-k] = v

Ans = 0
A,B = max(A,B),min(A,B)
for ai in range(N+1):
    bi = (K-A*ai)//B
    if 0<= bi <=N and A*ai + B*bi == K:
        Ans += C[ai] * C[bi]
        Ans %= MOD

print(Ans)

Submission status: Accepted

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

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
count=0
for i in range (N+1):
    if(((A+B)*N-A*i-K)%B==0):
        k=((A+B)*N-A*i-K)//B
        ca=cmb(N,i,mod)
        cb=cmb(N,k,mod)
        count=count+ca*cb
print(count%mod)

Submission status: Accepted

Solution code:
# coding: utf-8
def comb(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

n,a,b,k=map(int,input().split())
x=0
y=0
ans=0
mod = 998244353
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

while x<=n:
    if (k-a*x)%b==0:
        ans+=comb(n,x,mod)*comb(n,(k-a*x)//b,mod)
        ans%=998244353
    x+=1
print(ans)

Submission status: Accepted

Solution code:
SIZE=300000; MOD=998244353 #ここを変更する

inv = [0]*(SIZE+1)# inv[j] = j^{-1} mod MOD
fac = [0]*(SIZE+1)# fac[j] = j! mod MOD
finv = [0]*(SIZE+1)# finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
    

n,a,b,k = [int(i) for i in input().split()]
ans=0
for i in range(n+1):
    if (k-i*a)%b == 0:
        ans = (ans + choose(n,i)*choose(n,(k-i*a)//b)%MOD)%MOD
print(ans)

Submission status: Accepted

Solution code:
SIZE=300000; MOD=998244353 #ここを変更する

inv = [0]*(SIZE+1)# inv[j] = j^{-1} mod MOD
fac = [0]*(SIZE+1)# inv[j] = j! mod MOD
finv = [0]*(SIZE+1)# inv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if r < 0 or r > n or n < 0:
        return 0
    else:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    

n,a,b,k = [int(i) for i in input().split()]
ans=0
for i in range(n+1):
    if (k-i*a)%b == 0:
        ans = (ans + choose(n,i)*choose(n,(k-i*a)//b)%MOD)%MOD
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import array

SIZE=300000; MOD= 998244353
#inv = array.array('q',[0]*(SIZE+1))# inv[j] = j^{-1} mod M
#fac = array.array('q',[0]*(SIZE+1))# inv[j] = j! mod M
#finv = array.array('q',[0]*(SIZE+1))# inv[j] = (j!)^{-1} mod M
inv = [0]*(SIZE+1)# inv[j] = j^{-1} mod M
fac = [0]*(SIZE+1)# inv[j] = j! mod M
finv = [0]*(SIZE+1)# inv[j] = (j!)^{-1} mod M
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if r < 0 or r > n:
        return 0
    else:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    

n,a,b,k = [int(i) for i in input().split()]
ans=0
for i in range(n+1):
    if (k-i*a)%b == 0:
        ans = (ans + choose(n,i)*choose(n,(k-i*a)//b)%MOD)%MOD
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import array

SIZE=300000; MOD= 998244353
inv = array.array('q',[0]*(SIZE+1))# inv[j] = j^{-1} mod M
fac = array.array('q',[0]*(SIZE+1))# inv[j] = j! mod M
finv = array.array('q',[0]*(SIZE+1))# inv[j] = (j!)^{-1} mod M
#inv = [0]*(SIZE+1)# inv[j] = j^{-1} mod M
#fac = [0]*(SIZE+1)# inv[j] = j! mod M
#finv = [0]*(SIZE+1)# inv[j] = (j!)^{-1} mod M
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if r < 0 or r > n:
        return 0
    else:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    

n,a,b,k = [int(i) for i in input().split()]
ans=0
for i in range(n+1):
    if (k-i*a)%b == 0:
        ans = (ans + choose(n,i)*choose(n,(k-i*a)//b)%MOD)%MOD
print(ans)

Submission status: Accepted

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 <= N and f >= 0:
        ans = (ans + (nCr(N,i) * nCr(N,f))) % MOD
        
print(ans)
#239423 29392 39299 394239932

Submission status: Accepted

Solution code:
N = 3*10**5+1
MOD = 998244353

p = [1] * (N+1)
q = [1] * (N+1)

for i in range(1, N+1):
    p[i] = (p[i-1]*(i)%MOD)
q[0] = pow(p[-1], MOD-2, MOD)
for i in range(1, N+1):
    q[i] = (N-i+1)*q[i-1]%MOD
q.reverse()

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

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

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

Submission status: Accepted

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 or r==0:
    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)>=0:
    j=(K-A*i)//B
    if j <= N:
      ans+=( nCr(N,i) * nCr(N,j) ) %mod
      ans %= mod

print(ans)

Submission status: Accepted

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 + 1):
    if (K - (a * A) < 0):
        break
    if (K - (a * A)) % B == 0 and ((K - (a * A)) // B) <= N:
        pat += ncr[a] * ncr[(K - (a * A)) // B]
        pat %= mod

print(pat % mod)

Submission status: Accepted

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

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
fac_inv = [1]
for n in range (1,N+10):
    f = mul(fac[n-1], n)
    fac.append(f)
    fac_inv.append(inv(f))

mem = [0] * (N+1)
def ncr(n,r):
    if mem[r] > 0:
        return mem[r]
    else:
        ret = mul(mul(fac[n], fac_inv[n-r]), fac_inv[r])
        mem[r] = ret
        return ret

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    if b > N: continue
    ans += mul(ncr(N,a), ncr(N,b))
print(ans % MOD)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product

sys.setrecursionlimit(10000)

MOD = 998244353


def mul_mod(a, b):
    return (a % MOD) * (b % MOD) % MOD


def add_mod(a, b):
    return (a + b) % MOD


def sub_mod(a, b):
    return (a - b) % MOD


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


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


@mt
def slv(N, A, B, K):
    ans = 0

    FN, invs = prepare(N)
    for i in range(K // A + 1):
        if (K - i * A) % B == 0 and i <= N and (K - i * A) // B <= N:
            j = (K - i * A) // B
            error_print(i, j)
            ans = add_mod(ans,
                          mul_mod(FN * invs[i] * invs[N - i] % MOD,
                                  FN * invs[j] * invs[N - j] % MOD))

    return ans


def main():
    N, A, B, K = read_int_n()
    print(slv(N, A, B, K))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,a,b,k = (int(i) for i in input().split())
mod,ans = 998244353,0
fn,fk = [1]*n,[1]*n
for i in range(n-1): fn[i+1] = (fn[i]*(i+2))%mod
def power(n,k):
	if k==1: return n
	elif k%2==0: return power((n**2)%mod,k//2)
	else: return (n*power(n,k-1))%mod
def comb(n,k):
	if n==0 or k==0 or n==k: return 1
	else: return (((fn[n-1]*fk[n-k-1])%mod)*fk[k-1])%mod
fk[-1] = power(fn[-1],mod-2)
for i in range(2,n+1): fk[-i] = (fk[-i+1]*(n+2-i))%mod
for i in range(n+1):
	if (k-a*i)%b==0 and k-a*i>=0 and (k-a*i)//b<=n:
		j = (k-a*i)//b
		ans = (ans+(comb(n,i)*comb(n,j))%mod)%mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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+1):
	if (K - (a * A) < 0):
		break
	if (K - (a * A)) % B == 0 and ((K - (a * A))//B) <= N:
		pat += ncr[a]*ncr[(K - (a * A))//B]
		pat %= mod

print(pat % mod)

Submission status: Accepted

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 or y < 0:
        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: Accepted

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):
        y, m = divmod(K - A * x, B)
        if m == 0 and 0 <= y <= N:
            ans = ans + ct[min(x, N-x)] * ct[min(y, N-y)]
            ans = ans % mod
    return ans

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

Submission status: Accepted

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 b in range(N+1):
  a = (K-b*B)//A
  if 0 <= a <= N and a*A+b*B == K:
    sum += memo[a]*memo[b]
    sum %= sprime

print(sum)

Submission status: Accepted

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+1):
    if (K-A*i)%B==0 and K-A*i>=0:
        j=(K-A*i)//B
        if 0<=j<=N:
            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: Accepted

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
        if  max(n_a, n_b) <=n:
            ans+=com(n, n_a, mod) * com(n, n_b, mod)  %mod

print(ans%mod)

Submission status: Accepted

Solution code:
N, A, B, K = [int(_) for _ in input().split()]

L = 300000+1
M = 998244353

Fm = {}
inverseFm = {}
x = 1
for i in range(L):
    Fm[i] = x
    x = x * (i + 1) % M

def inverseFm(x, cache={}):
    if x in cache:
        return cache[x]
    result = pow(Fm[x], M - 2, M)
    cache[x] = result
    return result

def C(n, r):
    result = Fm[n] * inverseFm(r) * inverseFm(n - r) % M
    return result

def solve(N, A, B, K):
    result = 0
    for a in range(0, N+1):
        b, m = divmod(K - A * a, B)
        if m == 0 and 0 <= b <= N:
            result += C(N, a) * C(N, b) % M
    return result % M

print(solve(N, A, B, K))

Submission status: Accepted

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

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

ans = 0
for a in range(N+1):
    if (K - a*A) >= 0 and (K - a*A) % B == 0:
        b = (K - a*A) // B
        if not 0 <= b <= N:
            continue
        ans += rev[a]*rev[N-a] * rev[b]*rev[N-b]
        ans %= MOD
ans *= fact[N]*fact[N]
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, a, b, k = map(int, raw_input().split())
    mod = 998244353
    f = [1] * 300010
    invf = [1] * 300010
    for i in xrange(300000):
        f[i+1] = f[i] * (i + 1) % mod
    invf[300000] = pow(f[300000], mod - 2, mod)
    for i in xrange(300000, 1, -1):
        invf[i-1] = invf[i] * i % mod
    ans = 0
    for i in xrange(n + 1):
        if k < a * i:
            break
        if (k - a * i) % b == 0:
            t = (k - a * i) / b
            if t > n:
                continue
            ans += f[n] * invf[i] * invf[n-i] % mod * f[n] * invf[t] * invf[n-t] % mod
            if ans >= mod:
                ans -= mod
    print ans
main()

Submission status: Accepted

Solution code:
def gcd(a,b):
	if a > b:
		n,m = a,b
	else:
		n,m = b,a
	while m > 0:
		t = n % m
		n = m
		m = t
	return n

def gcd_3(a,b,c):
	return gcd(gcd(a,b),c)

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル

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

N,A,B,K = map(int,input().split())
g = gcd_3(A,B,K)
A = A // g
B = B // g
K = K // g
mod = 998244353 #出力の制限
inverse = [0, 1] #逆元テーブル計算用テーブル

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

ans = 0
n0,m0=-1,-1
for i in range(K//A + 1):
	if (K - A*i) % B == 0:
		n0,m0 = i, (K - A*i)//B
		break
k = 0
while k*B + n0 <= N and m0 - k*A >= 0:
	n,m = k*B + n0, m0 - k*A
	if m <= N:
		ans = (ans + cmb(N,n,mod) * cmb(N,m,mod)) % mod
	k += 1
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def inv(x):
    return pow(x, mod - 2, mod)

nm = {}
nm[0] = 1
def nCr_(n):
    b = n // 2 + 1
    r = 1
    d = 1
    for k in range(1,b+1):
        r = r * (n-k+1) % mod
        d = d * k % mod
        nm[k] = r * inv(d) % mod

def nCr(n, b):
    if b > n - b:
        b = n - b
    return nm[b]

def main():
    n,a,b,k = LI()
    r = 0
    nCr_(n)
    for i in range(n+1):
        ai = a * i
        bi = k - ai
        if bi < 0 or bi % b > 0 or bi // b > n:
            continue
        bb = bi // b
        r += nCr(n,i) * nCr(n,bb)
        r %= mod

    return r


print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
MOD = 998244353

fact = [1] * 300001
ifact = [1] * 300001
for i in range(1, 300001):
    fact[i] = (fact[i-1] * i) % MOD
    ifact[i] = pow(fact[i], MOD-2, MOD)


def nCk(n, k):
    if k < 0 or k > n: return 0
    return (fact[n] * ifact[n-k] * ifact[k]) % MOD

def solve(f):
    n, a, b, k = f.read_int_list()
    ans = 0

    for ai in xrange(n+1):
        res = k - a*ai
        if res < 0 or res%b != 0: continue
        bi = res/b
        ans = (ans + nCk(n, ai)*nCk(n, bi))%MOD

    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

Solution code:
MOD = 998244353

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

A,B = sorted((A,B))

if (A+B)*N < K:
  print(0)
  exit()

# tabulate combinations



# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
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)


# mを法とするaの乗法的逆元
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

cnt = 0

for b in range(N+1):
  a = (K-b*B)//A
  if 0 <= a <= N and a*A+b*B == K:
    cnt += memo[a]*memo[b]
    cnt %= MOD

print(cnt)

Submission status: Accepted

Solution code:
MOD = 998244353

f_list = [1] * 300000
f_r_list = [1] * 300000

for i in range(299999):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, 300001):
	f_r_list[-i] = int((f_r_list[-i + 1] * (300002 - i)) % MOD)

def comb(n, r):
	if n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 


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

cmb = []

for i in range(n+1):
	if (k - b * i) % a == 0 and k >= b * i and (k - b * i) // a <= n:
		cmb.append(((k - b * i) // a, i))

if cmb == []:
	print(0)
else:

	ans = 0

	for c in cmb:
		ans = int((ans + (comb(n, c[0]) * comb(n, c[1])) % MOD) % MOD)

	print(ans)