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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


# BEGIN CUT HERE
MOD = 10**9 + 7
# MOD = 998244353 # AGC025_B


class Modint():
    '''
    自動でMODで割った余りを計算してくれる整数。MODは素数である必要があり，デフォルトは10**9+7。
    Parameters
    ----------
    n (int): Modintの初期値
    MOD=10**9+7 (int): 余りを計算するMOD。素数である必要がある。
    '''

    def __init__(self, n, mod=MOD):
        if n >= 0:
            self.n = n % mod
        else:
            self.n = (mod - (-n) % mod) % mod
        self.mod = mod

    def __eq__(self, other):
        return self.n == int(other)

    def __ne__(self, other):
        return not self == other

    def __neg__(self):
        return self.__class__(-self.n, self.mod)

    def __str__(self):
        return str(self.n)

    def __int__(self):
        return int(self.n)

    def __iadd__(self, other):
        self.n += int(other)
        self.n %= self.mod
        return self

    def __radd__(self, other):
        self.n += int(other)
        self.n %= self.mod
        return self

    def __isub__(self, other):
        self.n -= int(other)
        self.n %= self.mod
        return self

    def __rsub__(self, other):
        self.n -= int(other)
        self.n %= self.mod
        return self

    def __imul__(self, other):
        self.n = self.n * int(other) % self.mod
        return self

    def __rmul__(self, other):
        self.n = self.n * int(other) % self.mod
        return self

    def inverse(self):
        '''
        フェルマーの小定理を考えると，MOD-2乗することでMODでの逆元を求めることができる。これは組み込み関数のpowを使うと十分に早い（O(log MOD)）。
        '''
        return pow(self.n, self.mod - 2, self.mod)

    def __ifloordiv__(self, other):
        self *= pow(int(other), self.mod - 2, self.mod)
        return self

    def __rfloordiv__(self, other):
        self *= pow(int(other), self.mod - 2, self.mod)
        return self

    def __add__(self, other):
        self += other
        return self

    def __sub__(self, other):
        self -= other
        return self

    def __mul__(self, other):
        self *= other
        return self

    def __floordiv__(self, other):
        self //= other
        return self

    def comb(self, n: int, k: int):
        '''
        コンビネーション絡みの定義。comb(n,k):特に前処理をせずnCkを求める
        毎回O(N)かかるので死ぬ覚悟でO(N^2)を投げるくらいしか無理

        ちなみにですが，これでABC132_D()を出すとPyPy3で1932msくらいですれすれセーフ
        '''
        if n < k or k < 0:
            return Modint(0)
        res = Modint(1)
        for i in range(int(k)):
            res *= Modint(n - i)
            res //= Modint(i + 1)
        return res

    def H(self, n: int, k: int):
        if n < 0 or k < 0:
            return Modint(0)
        elif n == 0 and k == 0:
            return Modint(1)
        else:
            return self.comb(n + k - 1, n)


class Combination():
    def __init__(self, sz):
        '''
        前処理にO(N)，それぞれの計算はO(1)。N = 200000なら割と余裕で通る。
        '''
        self._fact = [0] * (sz + 1)
        self._rfact = [0] * (sz + 1)
        self._fact[0] = 1
        self._rfact[sz] = 1
        for i in range(1, sz + 1):
            self._fact[i] = int(self._fact[i - 1] * Modint(i))
        self._rfact[sz] = Modint(self._fact[sz]).inverse()
        for i in range(sz - 1, -1, -1):
            self._rfact[i] = int(self._rfact[i + 1] * Modint(i + 1))

    def fact(self, k: int) -> int:
        return self._fact[k]

    def rfact(self, k: int) -> int:
        return self._rfact[k]

    def P(self, n: int, k: int) -> Modint:
        '''
        nPkの値を返す。nはあらかじめ前処理されたN以下でないとダメ
        Parameters
        ----------
        n (int): nPkのn(0<=n<=N)
        k (int): nPkのk（0<=k<=n）
        Returns
        ----------
        Modint: nPkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return 0
        return Modint(self._fact[n] * self._rfact[n - k])

    def C(self, n: int, k: int) -> Modint:
        '''
        nCkの値を返す。nはあらかじめ前処理されたN以下でないとダメ
        Parameters
        ----------
        n (int): nCkのn(0<=n<=N)
        k (int): nCkのk（0<=k<=n）
        Returns
        ----------
        Modint: nCkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return 0
        return Modint(self._fact[n] * self._rfact[k] * self._rfact[n - k])

    def H(self, n: int, k: int) -> Modint:
        '''
        nHkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        ちなみにnHkはn個の区別できないものをk個の箱に分けるパターンの数で，結局n+k-1Cnになる。
        Parameters
        ----------
        n (int): nHkのn(0<=n<=N)
        k (int): nHkのk（0<=k<=n）
        Returns
        ----------
        Modint: nHkをModint型で返す。Modintに依存。
        '''
        if n < 0 or k < 0:
            return 0
        elif k == 0:
            return 1
        return self.C(n + k - 1, n)

# END CUT HERE


def ABC132_D():
    N, K = mi()
    res = Combination(N)
    for i in range(1, K + 1):
        print(res.C(K - 1, i - 1) * res.H(N - K - i + 1, i + 1))
# verified on 2019/07/01
# https://atcoder.jp/contests/abc132/tasks/abc132_d
# Python3: 32ms https://atcoder.jp/contests/abc132/submissions/6200580


def AGC025_B():
    N, A, B, K = mi()
    res = Combination(N)
    ans = Modint(0)
    for a in range(K // A + 1):
        b = (K - a * A) // B
        if A * a + B * b == K and a >= 0 and b >= 0:
            ans += res.C(N, a) * res.C(N, b)
    print(ans)
# verified on 2019/07/01
# https://atcoder.jp/contests/agc025/tasks/agc025_b
# Python3: 


if __name__ == '__main__':
    # ABC132_D()
    AGC025_B()

Submission status: Wrong Answer

Solution code:
n, a, b, k = map(int, input().split())
mod = 998244353
ans = 0
ccn = [0]*(n+1)
ccn[0] = 1
for i in range(1,n+1):
  ccn[i] = ccn[i-1]*(n+1-1)//i%mod
for i in range(min(k//a,n)+1):
  jof = k-a*i
  if jof%b==0 and jof<=n*b:
    j = jof//b
    ans += ccn[i]*ccn[j]%mod
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
class BinomialCoefficient:
    def __init__(self, N, mod):
        '''
        Preprocess for calculating binomial coefficients nCr (0 <= r <= n, 0 <= n <= N)
        over the finite field Z/(mod)Z.
        Input:
            N (int): maximum n
            mod (int): a prime number. The order of the field Z/(mod)Z over which nCr is calculated.
        '''
        self.mod = mod
        self.fact = {i: None for i in range(N+1)}                # n!
        self.inverse = {i: None for i in range(1, N+1)}      # inverse of n in the field Z/(MOD)Z
        self.fact_inverse = {i: None for i in range(N+1)} # inverse of n! in the field Z/(MOD)Z
        
        # preprocess
        self.fact[0] = self.fact[1] = 1
        self.fact_inverse[0] = self.fact_inverse[1] = 1
        self.inverse[1] = 1
        for i in range(2, N+1):
            self.fact[i] = i * self.fact[i-1] % self.mod
            q, r = divmod(self.mod, i)
            self.inverse[i] = (- (q % self.mod) * self.inverse[r]) % self.mod
            self.fact_inverse[i] = self.inverse[i] * self.fact_inverse[i-1] % self.mod
    
    def binom(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return self.fact[n] * (self.fact_inverse[r] * self.fact_inverse[n-r] % self.mod) % self.mod
        
N, A, B, K = map(int, input().split())
MOD = 998244353

ans = 0
bc = BinomialCoefficient(N, MOD)
for red, i in [(A*i, i) for i in range(N+1)]:
    if K < red:
        break
    j, rem = divmod(K - red, B)
    if rem == 0:
        ans += (bc.binom(N, i) * bc.binom(N, j)) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
class BinomialCoefficient:
    def __init__(self, N, mod):
        '''
        Preprocess for calculating binomial coefficients nCr (0 <= r <= n, 0 <= n <= N)
        over the finite field Z/(mod)Z.
        Input:
            N (int): maximum n
            mod (int): a prime number. The order of the field Z/(mod)Z over which nCr is calculated.
        '''
        self.mod = mod
        self.fact = {i: None for i in range(N+1)}                # n!
        self.inverse = {i: None for i in range(1, N+1)}      # inverse of n in the field Z/(MOD)Z
        self.fact_inverse = {i: None for i in range(N+1)} # inverse of n! in the field Z/(MOD)Z
        
        # preprocess
        self.fact[0] = self.fact[1] = 1
        self.fact_inverse[0] = self.fact_inverse[1] = 1
        self.inverse[1] = 1
        for i in range(2, N+1):
            self.fact[i] = i * self.fact[i-1] % self.mod
            q, r = divmod(self.mod, i)
            self.inverse[i] = (- (q % self.mod) * self.inverse[r]) % self.mod
            self.fact_inverse[i] = self.inverse[i] * self.fact_inverse[i-1] % self.mod
    
    def binom(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return self.fact[n] * (self.fact_inverse[r] * self.fact_inverse[n-r] % self.mod) % self.mod
        
N, A, B, K = map(int, input().split())
MOD = 998244353

ans = 0
bc = BinomialCoefficient(N, MOD)
for red, i in [(A*i, i) for i in range(N+1)]:
    j, rem = divmod(max(K - red, 0), B)
    if rem == 0:
        ans += (bc.binom(N, i) * bc.binom(N, j)) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
class BinomialCoefficient:
    def __init__(self, N, mod):
        '''
        Preprocess for calculating binomial coefficients nCr (0 <= r <= n, 0 <= n <= N)
        over the finite field Z/(mod)Z.
        Input:
            N (int): maximum n
            mod (int): a prime number. The order of the field Z/(mod)Z over which nCr is calculated.
        '''
        self.mod = mod
        self.fact = {i: None for i in range(N+1)}                # n!
        self.inverse = {i: None for i in range(1, N+1)}      # inverse of n in the field Z/(MOD)Z
        self.fact_inverse = {i: None for i in range(N+1)} # inverse of n! in the field Z/(MOD)Z
        
        # preprocess
        self.fact[0] = self.fact[1] = 1
        self.fact_inverse[0] = self.fact_inverse[1] = 1
        self.inverse[1] = 1
        for i in range(2, N+1):
            self.fact[i] = i * self.fact[i-1] % self.mod
            q, r = divmod(self.mod, i)
            self.inverse[i] = (- (q % self.mod) * self.inverse[r]) % self.mod
            self.fact_inverse[i] = self.inverse[i] * self.fact_inverse[i-1] % self.mod
    
    def binom(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return self.fact[n] * (self.fact_inverse[r] * self.fact_inverse[n-r] % self.mod) % self.mod
        
N, A, B, K = map(int, input().split())
MOD = 998244353

ans = 0
bc = BinomialCoefficient(N, MOD)
for red, i in [(A*i, i) for i in range(N+1)]:
    j, rem = divmod(K - red, B)
    if rem == 0:
        ans += (bc.binom(N, i) * bc.binom(N, j)) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 998244353

def nCk(n, k):
  if n == k:
    return 1
  if n-k<k:
    k = n-k
  cc = 1
  for _ in range(k):
    cc *= n
    cc %= MOD
    n -= 1
  for i in range(2, k+1):
    cc *= pow(i, MOD-2, MOD)
    cc %= MOD
  return cc

n, a, b, k = map(int, input().split())
ans = 0
for i in range(n):
  rc = i
  if k - a*rc < 0:
    break
  if (k-a*rc)%b != 0:
    continue
  bc = (k-a*rc)//b
  ans += (nCk(n, rc) * nCk(n, bc)) % MOD
  ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
'''Snippets for combination.
Available functions:
- count_combination: Count the total number of combinations.
'''


def count_combination(n: int, r: int, mod: int = 10 ** 9 + 7) -> int:
    '''Count the total number of combinations.
        nCr % mod.
        nHr % mod = (n + r - 1)Cr % mod.
    Args:
        n   : Elements. Int of number (greater than 1).
        r   : The number of r-th combinations. Int of number (greater than 0).
        mod : Modulo. The default is 10 ** 9 + 7.
    Returns:
        The total number of combinations.
    Landau notation: O(n)
    See:
    https://qiita.com/derodero24/items/91b6468e66923a87f39f
    '''

    if r > (n - r):
        return count_combination(n, n - r, mod)

    if r == 0 or r == n:
        return 1

    if r == 1:
        return n

    multiple = 1
    division = 1

    for i in range(r):
        multiple *= n - i
        division *= i + 1
        multiple %= mod
        division %= mod

    return multiple * pow(division, mod - 2, mod) % mod


def main():
    n, a, b, k = map(int, input().split())
    mod = 998244353
    xy = list()
    ans = 0

    # See:
    # https://www.youtube.com/watch?v=Ommfmx2wtuY
    for x in range(n + 1):
        y, q = divmod(k - a * x, b)

        if y >= 0 and q == 0:
            xy.append((x, y))

    for x, y in xy:
        ans += count_combination(n, x, mod) * count_combination(n, y, mod)
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, A, B, k = list(map(int, input().split()))

MOD = 998244353
MAX = 3*10**5+2

fac = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]
ifac = [0 for i in range(MAX)]
fac[0] = 1; fac[1] = 1
inv[1] = 1
ifac[0] = 1; ifac[1] = 1

for i in range(2, MAX):
  fac[i] = fac[i-1]*i%MOD
  inv[i] = inv[MOD%i]*(MOD-MOD//i)%MOD
  ifac[i] = ifac[i-1]*inv[i]%MOD

def nCk(n, k):
  if n<k or n<0 or k<0: return 0
  return (((fac[n]*ifac[k])%MOD)*ifac[n-k])%MOD

ans = 0
for i in range(n+1):
  if (k-A*i)%B == 0:
    b = (k-A*i)//B
    if 0<=b<=n:
      ans = (ans+nCk(n, i)*nCk(n, b))%MOD

if ans==0:
  print(1)
else:
  print(ans)
print(nCk(4, 0))

Submission status: Wrong Answer

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

n,a,b,k=map(int,input().split())
m=998244353
count=0

g1=[1,1]
g2=[1,1]
inverse=[0,1]

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

for j1 in range(n):
  if (k-a*j1)%b==0 and (k-a*j1)//b<=n and (k-a*j1)>=0:
    j2=(k-a*j1)//b
    count+=cmb(n,j1,m)*cmb(n,j2,m)
  count%=m
print(count)

Submission status: Wrong Answer

Solution code:
def cmb(n,r):
  if n-r<r:r=n-r
  if r==0:return 1
  if r==1:return n

  numerator=[n-r+k+1 for k in range(r)]
  denominator=[k+1 for k in range(r)]

  for p in range(2,r+1):
    pivot=denominator[p-1]
    if pivot>1:
      offset=(n-r)%p
      for k in range(p-1,r,p):
        numerator[k-offset]/=pivot
        denominator[k]/=pivot

  result=1
  for k in range(r):
    if numerator[k]>1:
      result*=int(numerator[k])

  return result

n,a,b,k=map(int,input().split())
m=998244353
count=0
for i in range(n):
  if (k-a*i)%b==0 and (k-a*i)//b<=n:
    j=(k-a*i)//b
    count+=(cmb(n,i)%m)*(cmb(n,j)%m)
  count%=m
print(count)

Submission status: Wrong Answer

Solution code:
def cmb(n,r):
  if n-r<r:r=n-r
  if r==0:return 1
  if r==1:return n

  numerator=[n-r+k+1 for k in range(r)]
  denominator=[k+1 for k in range(r)]

  for p in range(2,r+1):
    pivot=denominator[p-1]
    if pivot>1:
      offset=(n-r)%p
      for k in range(p-1,r,p):
        numerator[k-offset]/=pivot
        denominator[k]/=pivot

  result=1
  for k in range(r):
    if numerator[k]>1:
      result*=int(numerator[k])

  return result

n,a,b,k=map(int,input().split())
m=998244353
count=0
for i in range(n):
  if (k-a*i)%b==0 and (k-a*i)//b<=n:
    j=(k-a*i)//b
    count+=(cmb(n,i)*cmb(n,j))%m
  count%=m
print(count)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 16 18:40:19 2019

@author: Yamazaki Kenichi
"""

N,A,B,K = map(int,input().split())
mod = 998244353
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
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inv = [0, 1] # 逆元テーブル計算用テーブル
for i in range(2, N+1):
    g1.append((g1[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inv[-1]) % mod)
def a(r,b):
    return cmb(N,r,mod)*cmb(N,b,mod)
ans = 0
R = K//A
for i in range(R):
    if (K-A*i)%B == 0:
        ans += a(i,(K-A*i)//B) % mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    def comb(a,b):
        return fact[a]*inv_fact[b]*inv_fact[a-b]%mod
    mod = 998244353
    n,a,b,k = LI()
    fact = [1]*(n+1)
    for i in range(1,n+1):
        fact[i] = fact[i-1]*i%mod
    inv_fact = [None]*(n+1)
    inv_fact[n] = pow(fact[n],mod-2,mod)
    for i in range(n)[::-1]:
        inv_fact[i] = inv_fact[i+1]*(i+1)%mod

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

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    def comb(a,b):
        return fact[a]*inv_fact[b]*inv_fact[a-b]%mod
    mod = 998244353
    n,a,b,k = LI()
    fact = [1]*(n+1)
    for i in range(1,n+1):
        fact[i] = fact[i-1]*i%mod
    inv_fact = [None]*(n+1)
    inv_fact[n] = pow(fact[n],mod-2,mod)
    for i in range(n)[::-1]:
        inv_fact[i] = inv_fact[i+1]*(i+1)%mod

    ans = 0
    for x in range(n):
        if (k-a*x)%b == 0 and k >= a*x and k-a*x <= n*b:
            y = (k-a*x)//b
            ans += comb(n,x)*comb(n,y)%mod
    print(ans)

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Wrong Answer

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

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q = m // n
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, m - q * n
    return x2, y2, n

MOD = 998244353  # type: int

def solve(N: int, A: int, B: int, K: int):
    N_max = 3*10**5
# 元テーブル
    g1 = [1, 1]
# 逆元テーブル
    g2 = [1, 1]
# 逆元テーブル計算用テーブル
    inv = [0, 1]

    for i in range(2, N_max+1):
        g1.append((g1[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD//i)) % MOD)
        g2.append((g2[-1] * inv[-1]) % MOD)


    x, y, gcd = extended_euclid(A, B)
    if K%gcd != 0:
        print(0)
        exit()

    x *= K//gcd
    y *= K//gcd

    if y>0:
        tmp = y//A
        x += B*tmp
        y = y%A
        if x < 0:
            print(0)
            exit()
    elif x>0:
        tmp = x//B
        y += A*tmp
        x = x%B
        if y < 0:
            print(0)
            exit()
        A, B, x, y = B, A, y, x
    ans = 0
    while x >= 0:
        if y > N or x > N or y < 0 or x < 0:
            break
        ans += g1[N]*g2[x]*g2[N-x] * g1[N]*g2[y]*g2[N-y] % MOD
        ans %= MOD
        y += A
        x -= B
    print(ans)

    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, A, B, K)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 16 15:50:39 2019

@author: Yamazaki Kenichi
"""

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

T = []
R = K//A
for i in range(R+1):
    if i == 0:
        if K%B == 0:
            T.append([0,0,K%B,N-K%B])
        continue
    if (K - (A*i)) % B == 0:
        r = i
        b = (K - (A*i)) // B
        g = min(r,b)
        r,b = r-g, b-g
        while r+g+b <=N and g>=0:
            T.append([r,g,b,N-(r+g+b)])
            r,g,b = r+1,g-1,b+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inv = [0, 1] # 逆元テーブル計算用テーブル
for i in range(2, N+1):
    g1.append((g1[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inv[-1]) % mod)

ans = 0
for c in T:
    ans += g1[N]*g2[c[0]]*g2[c[1]]*g2[c[2]]*g2[c[3]]%mod
print(ans%mod)

Submission status: Wrong Answer

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

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q = m // n
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, m - q * n
    return x2, y2, n

MOD = 998244353  # type: int

def solve(N: int, A: int, B: int, K: int):
    N_max = 3*10**5
# 元テーブル
    g1 = [1, 1]
# 逆元テーブル
    g2 = [1, 1]
# 逆元テーブル計算用テーブル
    inv = [0, 1]

    for i in range(2, N_max+1):
        g1.append((g1[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD//i)) % MOD)
        g2.append((g2[-1] * inv[-1]) % MOD)


    x, y, gcd = extended_euclid(A, B)
    if K%gcd != 0:
        print(0)
        exit()

    x *= K//gcd
    y *= K//gcd

    if y>0:
        tmp = y//A
        x += B*tmp
        y = y%A
        if x < 0:
            print(0)
            exit()
    elif x>0:
        tmp = x//B
        y += A*tmp
        x = x%B
        if y < 0:
            print(0)
            exit()
        A, B, x, y = B, A, y, x
    ans = 0
    while x >= 0:
        #print(x, y, A*x+B*y)
        for l in reversed(range(min(x, y)+1)):
            n = x - l
            m = y - l
            if n+m+l>N:
                break
            ans += g1[N]*g2[n]*g2[m]*g2[l]*g2[N-n-m-l]
            ans %= MOD
        y += A
        x -= B
    print(ans)

    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, A, B, K)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q = m // n
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, m - q * n
    return x2, y2, n

MOD = 998244353  # type: int

def solve(N: int, A: int, B: int, K: int):
    N_max = 3*10**5
# 元テーブル
    g1 = [1, 1]
# 逆元テーブル
    g2 = [1, 1]
# 逆元テーブル計算用テーブル
    inv = [0, 1]

    for i in range(2, N_max+1):
        g1.append((g1[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD//i)) % MOD)
        g2.append((g2[-1] * inv[-1]) % MOD)


    x, y, gcd = extended_euclid(A, B)
    if K%gcd != 0:
        print(0)
        exit()

    x *= K//gcd
    y *= K//gcd

    if y>0:
        tmp = y//A
        x += B*tmp
        y = y%A
        if x < 0:
            print(0)
            exit()
    if x>0:
        tmp = x//B
        y += A*tmp
        x = x%B
        if y < 0:
            print(0)
            exit()
        A, B, x, y = B, A, y, x
    ans = 0
    while x >= 0:
        #print(x, y, A*x+B*y)
        for l in range(min(x, y)+1):
            n = x - l
            m = y - l
            if n+m+l>N:
                continue
            ans += g1[N]*g2[n]*g2[m]*g2[l]*g2[N-n-m-l]
            ans %= MOD
        y += A
        x -= B
    print(ans)

    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, A, B, K)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/agc025/tasks/agc025_b

import itertools
import collections
import bisect


# Calculate count of combination
def combination(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
    return a // b


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

    ans = 0
    for a in range(N+1):
        if (K - a * A) % B != 0:
            continue
        b = (K - a * A) // B
        ans += (combination(N, a) * combination(N, b)) % 998244353

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = 998244353


def get_inv(n):
    inv = [0] * (n + 1)
    inv[1] = 1

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

    return inv


def get_cmb(n):
    inv = get_inv(n)
    cmb = [0] * (n + 1)
    cmb[0] = 1

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

    return cmb


def solve(n, a, b, k):
    ans = 0
    cmb = get_cmb(n)
    print(cmb)
    for a_num in range(n + 1):
        b_num = (k - a * a_num) // b
        if (a * a_num + b * b_num == k) and (0 <= b_num <= n):
            ans += (cmb[a_num] * cmb[b_num]) % MOD
            ans %= MOD
    return ans


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


main()

Submission status: Wrong Answer

Solution code:
mod=998244353
def fac(n):
    x=1
    for i in range(1,n+1):
        x*=i%mod
        x%=mod
    return x
def c(n,r):
    return (fac(n)//(fac(n-r)*fac(r))%mod)%mod

N,A,B,K=map(int,input().split())
ans=0
for a in range(N+1):
    if a*A>K:
        break
    if (K-a*A)%B==0 and a+(K-a*A)//B<=N:
        b=(K-a*A)//B
        for g in range(min(a,b)+1):
            ans+=(((c(N,g)*c(N-g,min(a,b)-g))%mod)*c(N-min(a,b),max(a,b)-g))%mod
            ans%=mod
print(ans%mod)

Submission status: Wrong Answer

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

mod = 998244353
fact = [1] + [0] * n
inv_fact = [0] * (n+1)
for i in range(n):
    fact[i+1] = (fact[i] * (i+1)) % mod

for i in range(n+1):
    inv_fact[i] = pow(fact[i],mod-2,mod)
    
def cb(n, k, mod):
    return (fact[n] * inv_fact[k] * inv_fact[n-k]) % mod

ans = 0
for x in range(max(0, (k-(n+1)*b)//a+1), min(n+1, k//a)):
    if (k-x*a) % b == 0:
        y = (k-x*a)//b
        if y >= 0:
            if x > n or y > n:
                pass
            else:
                ans += cb(n, x, mod) * cb(n, y, mod)
                ans %= mod
    
print(ans)

Submission status: Wrong Answer

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

Factorial=[1]*(N+1)
for i in range(1,N+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod

inverseFactorial=[1]*(N+1)
inverseFactorial[N]=power(Factorial[N],mod-2)
for i in range(0,N)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def f(i,j):
  if i>j:
    i,j=j,i
  res=0
  if j<=N:
    for k in range(max(0,i+j-N),i+1):
      res+=Factorial[N]*inverseFactorial[i-k]*inverseFactorial[j-k]*inverseFactorial[k]*inverseFactorial[N-i-j+k]
  return res%mod
      
ans=0
g=gcd(A,B)
if K%g==0:
  A,B,K=A//g,B//g,K//g
else:
  print(0)
  exit()
for i in range(K//A+1):
  if (K-A*i)%B==0:
    x0=i
    y0=(K-A*i)//B
    break
m=0
while y0-A*m>=0:
  ans+=f(x0+B*m,y0-A*m)
  ans%=mod
  m+=1
    
print(ans%mod-1)