Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import fractions
import math

def cf(x, y):
    cf = [1]
    for i in range(2, min(x,y)+1):
        if x % i == 0 and y % i == 0:
            cf.append(i)
    return cf

def comprime(a, b):
    return fractions.gcd(a, b) == 1

def is_prime(n):
    if n == 1 : return True

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

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

y = cf(A,B)

cnt = 0
for yi in y:
    if is_prime(yi):
        cnt += 1

print(cnt)


### FIXED CODE ###

from fractions import gcd
A,B = map(int, input().split())
g=gcd(A,B)
def prime_factorization(n):
    prime_num = []
    for i in range(2, int(n**.5)+1):
        num = 0
        while True:
            x,y = divmod(n, i)
            if y!= 0:
                break
            n = x
            num += 1
        if num>0:
            prime_num.append(i)
    if n > 1:
        prime_num.append(n)
    return prime_num
print(len(prime_factorization(g))+1)
### BUGGY CODE ###

N = int(input())
A, B = [], []
for i in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
  
x, y = 0, 0
for i in range(N//2):
  if A.index(max(A)) == B.index(max(B)):
    s = A.index(max(A))
    x += A[s]
    A.pop(s)
    B.pop(s)
    t = B.index(max(B))
    y += B[t]
    A.pop(t)
    B.pop(t)
  else:
    s = max(A)
    t = max(B)
    u = A[B.index(t)]
    w = sorted(B)[-2]
    if s-t >= u-w:
      x += s
      y += t
    else:
      x += u
      y += w
      
if N % 2 == 1:
  x += A[0]
print(x-y)


### FIXED CODE ###

N = int(input())
A, B = [], []
for i in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
  
l = []
for i in range(N):
  l.append(A[i]+B[i])
l.sort(reverse=True)

ans = 0
for i in range(N//2):
  ans += l[2*i]
if N % 2 == 1:
  ans += l[-1]
ans -= sum(B)
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())

root = [[pow(10,9)]*n for _ in range(n)]

from collections import deque

root=[0]*n
r=[[]for i in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    r[a].append(b)
    r[b].append(a)

dist =[-1]*n
dist[0] = 0

q = deque([0])
prev=[-1] * n

while q:
    v = q.popleft()

    for j in r[v]:
        if dist[j]!=-1:
            continue
        else:
            dist[j] = dist[v] + 1
            prev[j] = v
            q.append(j)


for i in range(n):
    if i==0:
        print('Yes')
    else:
        print(prev[i]+1)


### FIXED CODE ###

n,m = map(int,input().split())
from collections import deque
r=[[] for i in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    r[a].append(b)
    r[b].append(a)

# dist =[-1]*n
# dist[0] = 0

q = deque([0])
prev=[-1] * n

while q:
    v = q.popleft()

    for j in r[v]:
        if prev[j]==-1:
            prev[j] = v
            q.append(j)
            # dist[j] = dist[v] + 1
            

for i in range(n):
    if i==0:
        print('Yes')
    else:
        print(prev[i]+1)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
p=1
for i in a[:k]:
    p*=i
for i in range(k,len(a)):
    q=p*a[i]/a[i-k]
    if q>p: print("Yes")
    else: print("No")
    p=q


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(k,len(a)):
    if a[i]>a[i-k]: print("Yes")
    else: print("No")
### BUGGY CODE ###

n,m=map(int,input().split())
s=input()
t=input()

from fractions import gcd
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

long=lcm([n,m])

ln=int(long/n)
lm=int(long/m)

ans=[]
ok=True
for i in range(long):
    an=i%ln
    am=i%lm
    kn=i//ln
    km=i//lm
    if (an==0)&(am==0):
        if s[kn]==t[km]:
            ans.append(s[kn])
        else:ok=False
    elif an==0:
        ans.append(s[kn])
    elif am==0:
        ans.append(t[km])
    else:
        ans.append("a")
lll=len(ans)
if not ok:
    lll=-1

print(lll)

### FIXED CODE ###

n,m=map(int,input().split())
s=input()
t=input()

from fractions import gcd
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

long=lcm([n,m])

ln=int(long/n)
lm=int(long/m)

#ans=[]

ok=True

for i in range(n-1):
    if (i*ln)%lm==0:
        if s[i]!=t[(i*ln)//lm]:
            ok=False

if n==1:
    if s!=t[0]:ok=False
if m==1:
    if t!=s[0]:ok=False

if not ok:long=-1

print(long)
### BUGGY CODE ###

import sys

num, total = list(map(int, sys.stdin.read().split(" ")))
for i in range(total // 10000, -1, -1):
  amount = total - 10000 * i
  if amount == 0 and i == num:
    print("%d 0 0"%i)
    sys.exit(0)
  for j in range(amount // 5000, -1, -1):
    amountj = amount - 5000 * j
    if amountj == 0 and i+j == num:
      print("%d %d 0"%(i, j))
      sys.exit(0)
    for k in range(amountj // 1000, -1, -1):
      amountk = amountj - 1000 * k
      if amountk == 0 and i+j+k == num:
        print("%d %d %d"%(i, j, k))
        sys.exit(0)
print("-1 -1 -1")


### FIXED CODE ###

import sys

num, total = list(map(int, sys.stdin.read().split(" ")))
for i in range(total // 10000, -1, -1):
  amount = total - 10000 * i
  if amount == 0 and i == num:
    print("%d 0 0"%i)
    sys.exit(0)
  for j in range(amount // 5000, -1, -1):
    amountj = amount - 5000 * j
    if amountj == 0 and i+j == num:
      print("%d %d 0"%(i, j))
      sys.exit(0)
    k = amountj // 1000
    if i+j+k == num:
      print("%d %d %d"%(i, j, k))
      sys.exit(0)
print("-1 -1 -1")
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
 
for i in range(n):
  ans = ans * a[i]
    
if ans > 10**18:
  print(-1)
else:  
  print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1

if 0 in a:
  print(0)
  exit()
  
for i in range(n):
  ans = ans*a[i]
  if ans > 10**18:
    print(-1)
    exit()
    
print(ans)
### BUGGY CODE ###

from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch, Cw))

dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
wps = [
    [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -1), (-1, 1)],
    [(2, 2), (2, -1), (2, 0), (2, 1), (2, 2), (1, -1), (1, 1)],
    [(-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (-1, 1), (1, 1)],
    [(-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2), (-1, -1), (1, -1)]
]

while q:
    d, i, j = heappop(q)
    used.add((i, j))

    if D[i][j] > d:
        D[i][j] = d
    else:
        continue

    for k, (di, dj) in enumerate(dirs):
        _i = i + di
        _j = j + dj
        if 0 <= _i < H and 0 <= _j < W:
            if (_i, _j) in used:
                continue
            if S[_i][_j] == '.':
                used.add((_i, _j))
                heappush(q, (d, _i, _j))
            else:
                for di, dj in wps[k]:
                    _i = i + di
                    _j = j + dj
                    if 0 <= _i < H and 0 <= _j < W and (_i, _j) not in used and S[_i][_j] == '.':
                        heappush(q, (d+1, _i, _j))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)


### FIXED CODE ###

from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch*W+Cw))


while q:
    d, ij = heappop(q)
    i, j = divmod(ij, W)

    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            I = i+di; J = j+dj
            if 0 <= I < H and 0 <= J < W and S[I][J] == '.':
                if abs(di)+abs(dj) == 1:
                    if D[I][J] <= d:
                        continue
                    D[I][J] = d
                    heappush(q, (d, I*W+J))
                else:
                    if D[I][J] <= d+1:
                        continue
                    D[I][J] = d+1
                    heappush(q, (d+1, I*W+J))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)
### BUGGY CODE ###

n = int(input())
b = [''.join(sorted(input())) for i in range(n)]
c = list(set(b))
d = len(c)
cnt = [b.count(c[i]) for i in range(d)]
ans = 0
for i in cnt:
  ans += int(i*(i-1)/2)
print(ans)

### FIXED CODE ###

N = int(input())
s_sort = [''.join(sorted(input())) for _ in range(N)]
dic = {}
ans = 0
for i in s_sort:
  if i not in dic:
    dic[i] = 0
  else:
    dic[i] += 1
    ans += dic[i]
print(ans)
### BUGGY CODE ###

#C
import itertools
import numpy as np
n, m, q = list(map(int, input().split()))
a = np.zeros(q)
b = np.zeros(q)
c = np.zeros(q)
d = np.zeros(q)
ans = 0
for i in range(q):
    a[i], b[i], c[i], d[i] = list(map(int, input().split()))
for A in itertools.combinations_with_replacement(range(1,m+1),n):
    new_ans = 0
    for i in range(q):
        if A[int(b[i])-1] - A[int(a[i])-1] == c[i]:
            new_ans += d[i]
    ans = max(ans, new_ans)
print(int(ans))

### FIXED CODE ###

#C
import itertools
n, m, q = list(map(int, input().split()))
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q
ans = 0
for i in range(q):
    a[i], b[i], c[i], d[i] = list(map(int, input().split()))
for A in itertools.combinations_with_replacement(range(1,m+1),n):
    new_ans = 0
    for i in range(q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            new_ans += d[i]
    ans = max(ans, new_ans)
print(int(ans))
### BUGGY CODE ###

s = str(input())
q = int(input())
flip = -1
strs = '/'

for i in range(q):
    query = list(map(str, input().split()))
    if query[0] == '1':
        flip = flip * -1
    elif query[0] == '2':
        if query[1] == '1':
            if flip == -1:
                strs = query[2] + strs
            else:
                strs = strs + query[2]
        else:
            if flip == -1:
                strs = strs + query[2]
            else:
                strs = query[2] + strs

strs_f = ''
for i in range(len(strs)):
    if strs[i] == '/':
        break
    strs_f += strs[i]

strs_b = ''
for i in range(len(strs)-1, -1, -1):
    if strs[i] == '/':
        break
    strs_b += strs[i]

if flip == -1:
    ans = strs_f + s + strs_b[::-1]
else:
    ans = strs_b + s[::-1] + strs_f[::-1]

print(ans)

### FIXED CODE ###

from collections import deque

s = str(input())
q = int(input())
flip = -1
strf = deque()
strb = deque()

for i in range(q):
    query = list(map(str, input().split()))
    if query[0] == '1':
        flip = flip * -1
    elif query[0] == '2':
        if query[1] == '1':
            if flip == -1:
                strf.appendleft(query[2])
            else:
                strb.append(query[2])
        elif query[1] == '2':
            if flip == -1:
                strb.append(query[2])
            else:
                strf.appendleft(query[2])

# print(strf)
# print(strb)
ans = ''.join(strf) + s + ''.join(strb)
if flip == 1:
    ans = ans[::-1]
print(ans)

# s = str(input())
# q = int(input())
# flip = -1
# strs = '/'
 
# for i in range(q):
#     query = list(map(str, input().split()))
#     if query[0] == '1':
#         flip = flip * -1
#     elif query[0] == '2':
#         if query[1] == '1':
#             if flip == -1:
#                 strs = query[2] + strs
#             else:
#                 strs = strs + query[2]
#         else:
#             if flip == -1:
#                 strs = strs + query[2]
#             else:
#                 strs = query[2] + strs
 
# if flip == -1:
#     ans = strs.replace('/', s)
# else:
#     ans = strs[::-1].replace('/', s[::-1])
 
# print(ans)
### BUGGY CODE ###

#comb_mod(n, r, mod) = nCr % mod
def comb_mod(n, r, mod):
    ans = 1
    if r <= n/2:
        for i in range(n-r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    else:
        for i in range(r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, n-r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    return ans

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

ans = 0
for i in range(n-k+1):
    ans += (a[-(i+1)] - a[i]) * comb_mod(n-i-1, k-1, 10**9+7)
print(ans % (10**9+7))

### FIXED CODE ###

#comb_mod(n, r, mod) = nCr % mod
def comb_mod(n, r, mod):
    ans = 1
    if r <= n/2:
        for i in range(n-r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    else:
        for i in range(r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, n-r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    return ans

#comb(n,r) = nCr
def comb(n, r):
    m = 1
    for i in range(n-r+1, n+1):
        m *= i
    for i in range(1, r+1):
        m //= i
    return m

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

ans = 0
pattern = comb_mod(n-1, k-1, 10**9+7)
for i in range(n-k+1):
    ans += (a[-(i+1)] - a[i]) * pattern
    pattern *= (n-k-i) * pow(n-1-i, 10**9+5, 10**9+7)
    pattern %= 10**9 + 7
print(ans % (10**9+7))
### BUGGY CODE ###

'''
.append(要素) リストに要素を追加 
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
import itertools
from functools import reduce
from operator import mul

f = [int(s) for s in stdin.readline().rstrip().split()]
N = f[0]
K = f[1]
p = [int(s) for s in stdin.readline().rstrip().split()]
past = -2000
resNum = -2000
for el in range(N - K + 1):
    data = copy.copy(p)
    if past < sum(data[el: el + K]):
        past = sum(data[el: el + K])
        resNum = el
res = p[resNum: resNum + K]
result = 0
for el in res:
    result += (1/2+el/2)
print(result)


### FIXED CODE ###

'''
.append(要素) リストに要素を追加 
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
import itertools
from functools import reduce
from operator import mul

f = [int(s) for s in stdin.readline().rstrip().split()]
N = f[0]
K = f[1]
p = list(map(lambda x: 1/2+x/2, [int(s)
                                 for s in stdin.readline().rstrip().split()]))
E = []
tmp = 0
for el in p:
    tmp += el
    E.append(tmp)
past = E[K - 1]
for el in range(len(E)):
    if el - K < 0:
        continue
    e = E[el] - E[el - K]
    if past < e:
        past = e
print(past)
### BUGGY CODE ###

def main():
    N = input()
    L = [int(i) for i in input().split()]

    sL = sorted(L)
    ans = []

    for num in sL:
        print(L.index(num) + 1, end=" ")

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N = input()
    L = [int(i) for i in input().split()]
    
    siL = sorted(range(len(L)), key=lambda k: L[k])
    for i in siL:
        print(i + 1, end=" ")

if __name__ == "__main__":
    main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))

b=[0 for i in range(n)]
res=0
for i in range(n):
    print(a.count(i+1))


### FIXED CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))

b=collections.Counter(a)
for i in range(1,n+1):
    print(b[i])
### BUGGY CODE ###

N,K = map(int,input().split())
a = list(map(int,input().split()))
t = []; u = 1
for i in range(K):
    u *= a[K-i-1]
t.append(u)
for i in range(1,N-K+1):
    u = u / a[i-1]
    u = u * a[K+i-1]
    t.append(u)
    if t[i-1]<t[i]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N,K = map(int,input().split())
a = list(map(int,input().split()))
for i in range(1,N-K+1):
    if a[K+i-1]>a[i-1]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n=int(input())
mod=10**9+7
a=list(map(int,input().split()))
ans=0
for i in range(60):
    ichi=0
    for j in range(n):
        if (a[j]>>i)&1:
            ichi+=1
    zero=n-ichi
    s=ichi*zero*2**i%mod# xorをしたあとi桁目が1になる組み合わせの個数 x 2**i
    ans+=s
    ans%=mod
print(ans)


### FIXED CODE ###

n=int(input())
mod=10**9+7
a=list(map(int,input().split()))
ans=0
for i in range(60):
    ichi=0
    for j in range(n):
        if (a[j]>>i)&1:
            ichi+=1
    zero=n-ichi
    s=ichi*zero*pow(2,i,mod)%mod# xorをしたあとi桁目が1になる組み合わせの個数 x 2**i
    ans+=s
    ans%=mod
print(ans)
### BUGGY CODE ###

K, S = map(int, input().split())

num = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                num += 1
                
print(num)


### FIXED CODE ###

K, S = map(int, input().split())

num = 0
for x in range(K+1):
    for y in range(K+1):
#        for z in range(K+1):
#            if x + y + z == S:
        if 0 <= S - x- y <= K:
            num += 1
                
print(num)
### BUGGY CODE ###

def fact(n):
    L = []
    i = 1
    while i*i <= n:
        if n % i == 0:
            L.append(i)
        i += 1
    return L

X = int(input())
N = -X if X < 0 else X
L = fact(N)
for e in L:
    if pow(e, 5, 5) !=  N%5: continue
    b = -e
    while True:
        a = b+e
        if a**5 - b**5 == N:
            ans = (b, a) if X < 0 else (a, b)
            print(str(ans[0]), str(ans[1]))
            exit()
        b += 1

### FIXED CODE ###

X = int(input())
for A in range(-118, 120):
    for B in range(-119, 119):
        if A**5-B**5 == X:
            print(A, B)
            exit()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
vs = set()
def dfs_w(d, stack):
    depth = [-1] + [0]*N
    pvs = set()
    while stack:
        v, dpd = stack.pop()
        vs.add(v)
        pvs.add(v)

        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack += [(u, dpd)]

    return True

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i+1 in vs:
            continue
        stack = [(i+1, 0)] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

import sys
input = sys.stdin.readline
vs = set()
def dfs_w(d, stack):
    depth = defaultdict(int)
    pvs = set()
    while stack:
        v = stack.pop()
        vs.add(v)
        pvs.add(v)
        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack.append(u)
    return True

if __name__ == '__main__':
    from collections import defaultdict
    N, M = map(int, input().split())
    G = defaultdict(set)
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i+1 in vs:
            continue
        stack = [i+1] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")
### BUGGY 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 = {}
def nCr(n, b):
    if b > n - b:
        b = n - b
    if b in nm:
        return nm[b]
    r = 1
    for k in range(n, n-b, -1):
        r = r * k % mod
    d = 1
    for k in range(1, b+1):
        d = d * k % mod
    nm[b] = r * inv(d) % mod
    return nm[b]

def main():
    n,a,b,k = LI()
    r = 0
    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())



### FIXED 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())
### BUGGY CODE ###

import numpy as np
n=int(input())
takahashi=[]
aoki=[]
gohan=[]
kouhuku_t=0
kouhuku_a=0
for i in range(n):
    a,b=map(int,input().split())
    takahashi.append(a)
    aoki.append(b)
    gohan.append(a+b)
for i in range(n):
    if i%2==0:
        count=np.argmax(gohan)
        kouhuku_t+=takahashi.pop(count)
        del aoki[count]
    else:
        count=np.argmax(aoki)
        kouhuku_a+=aoki.pop(count)
        del takahashi[count]
    del gohan[count]
print(kouhuku_t-kouhuku_a)

### FIXED CODE ###

n = int(input())
c = []#料理Nに対する高橋くんと青木さんの幸福度の和？
bs = 0#全ての料理を青木さんが食べたと仮定した時の青木さんの幸福度
for i in range(n):
    a,b = map(int,input().split())
    bs += b
    c.append(a+b)

c.sort()#Cを昇順ソート
c.reverse()#降順に直す

ans = -bs
for i in range(n):
    if i%2==0: ans += c[i]#高橋くんが食べる時、引いた青木さんの幸福度(食べてないのでいらない)と高橋くんの幸福度を足す
print(ans)
### BUGGY CODE ###

from fractions import gcd

n = int(input())
a = list(map(int, input().split()))

l = [a[0]]
r = [a[-1]]
for i in range(n-1):
  l.append(gcd(l[-1], a[i+1]))
  r.insert(0, gcd(r[0], a[-2-i]))

maxi = max(l[-2], r[1])
for i in range(1, n-1):
  maxi = max(maxi, gcd(l[i-1], r[i+1]))
print(maxi)


### FIXED CODE ###

from fractions import gcd

n = int(input())
a = list(map(int, input().split()))

l = [a[0]]
r = [a[-1]]
for i in range(n-1):
  l.append(gcd(l[-1], a[i+1]))
  r.append(gcd(r[-1], a[-2-i]))
r = r[::-1]

maxi = max(l[-2], r[1])
for i in range(1, n-1):
  maxi = max(maxi, gcd(l[i-1], r[i+1]))
print(maxi)