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

#template
def inputlist(): return [int(j) for j in input().split()]
#template

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


N,M = inputlist()
uf = UnionFind(N+1)
for i in range(M):
    A,B = inputlist()
    uf.union(A,B)

ans = 0
lis = uf.all_group_members()
key = uf.roots()
for i in key:
    ans = max(ans,len(list(lis[i])))
print(ans)

### FIXED CODE ###

#template
def inputlist(): return [int(j) for j in input().split()]
#template

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


N,M = inputlist()
uf = UnionFind(N+1)
for i in range(M):
    A,B = inputlist()
    uf.union(A,B)

ans = 0
for i in range(N+1):
    ans = max(ans,uf.size(i))
print(ans)
### BUGGY CODE ###

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

b = []
r = 1

b.append(a[0])
for i in range(1, n):
    if(r == 1):
        b.append(a[i])
        r = 0
    elif(r == 0):
        b.insert(0, a[i])
        r = 1
    else:
        pass

if(n % 2 == 0):
    b.reverse()
    

print(*b)


### FIXED CODE ###

from collections import *
n = int(input())
a = [int(i) for i in input().split()]

b = deque()

b.append(a[0])
for i in range(1, n):
    if(i%2 == 1):
        b.append(a[i])  
    else:
        b.appendleft(a[i])
   

if(n % 2 == 0):
    b.reverse()
    

print(' '.join(map(str, b)))
### BUGGY CODE ###

n=int(input())
A=sorted([int(i) for i in input().split()])
B=sorted([int(i) for i in input().split()])
C=sorted([int(i) for i in input().split()])
a=[]
b=[]
for i in range(n):
    count=0
    for j in range(n):
        if A[i]<B[j]:
            count+=1
    a.append(count)
for i in range(n):
    count=0
    for j in range(n):
        if B[i]<C[j]:
            count+=1
    b.append(count)
ans=0
for i in range(n):
    if a[i]!=0:
        for j in range(n-a[i],n):
            ans+=b[j]
#            print(ans)
print(ans)
#print(a)
#print(b)

### FIXED CODE ###

import bisect
n=int(input())
abc=[sorted(list(int(i) for i in input().split())) for i in range(3)]
print(sum([bisect.bisect_left(abc[0],b)*(n-bisect.bisect_right(abc[2],b)) for b in abc[1]]))
### BUGGY CODE ###

#ABC129C-TypicalStairs.py

#import list
from sys import stdin
from functools import lru_cache

input = stdin.readline

#constant
#N = int(input())
N, M = list(map(int,input().split()))
A = [int(input()) for _ in range(M)]+[N+1]

#variable

#function
@lru_cache(maxsize=None)
def partition(two_steps,total_steps):
    if two_steps == 0:
        return 1
    elif two_steps == 1:
        return total_steps-1
    else:
        result = 0
        for i in range(total_steps-(2*(two_steps-1))):
            result += partition(two_steps-1,total_steps-(i+2))
        return result

@lru_cache(maxsize=None)
def sectorSum(total_steps):
    if total_steps == 0:
        return 0
    result = 0
    max_two_steps = total_steps//2
    for two_steps in range(max_two_steps+1):
        result += partition(two_steps,total_steps)
    return result
#class

#main function
def main():
    totalResult = 1
    position = 0
    i = 0
    while position < N:
        a = A.pop(0)
        if position+1 == a:
            position = a+1
            if position == A[0]:
                totalResult = 0
                break
        else:
            totalResult = totalResult*sectorSum(a-1-position)
            position = a+1
    print(totalResult%1000000007)




if __name__ == "__main__":
    main()


### FIXED CODE ###

#ABC129C-TypicalStairs.py

#import list
import numpy as np
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(1000)

#constant
#N = int(input())
N, M = list(map(int,input().split()))
A = {int(input()) for _ in range(M)}

#variable
rootList = np.array([1]+[0]*(N))

#function

#class

#main function
def main():
    for i in range(N):
        rootList[i+1] = (rootList[i]+rootList[i-1])%1000000007
        if i+1 in A:
            rootList[i+1] = 0
    print(rootList[N])

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

N, M = map(int, input().split())
A = []
for i in range(M):
    A.append(list(map(int,input().split())))
A = A[::-1]


P = [[x+1] for x in range(N)]
n = [x+1 for x in range(N)]
an = [N*(N-1)/2]


for i in range(M-1):
    if an[i] == 0:
        an.append(0)
    else:        
        Aind = A[i][0]-1
        Bind = A[i][1]-1
        PAind = P[n[Aind]-1]
        PBind = P[n[Bind]-1]
        if n[Aind] != n[Bind]:
            an.append(an[i]-len(PAind) * len(PBind))
            P[n[Aind]-1].extend(PBind)
            for j in PBind:
                n[j-1] = n[Aind]
        else:
            an.append(an[i])
            
        
an = an[::-1]
for k in range(M):
    print(int(an[k]))

### FIXED CODE ###

N, M = map(int, input().split())
A = []
for i in range(M):
    A.append(list(map(int,input().split())))
A = A[::-1]


P = [[x+1] for x in range(N)]
n = [x+1 for x in range(N)]
an = [N*(N-1)/2]


for i in range(M-1):
    if an[i] == 0:
        an.append(0)
    else:        
        Aind = A[i][0]-1
        Bind = A[i][1]-1
        PAind = P[n[Aind]-1]
        PBind = P[n[Bind]-1]
        if n[Aind] != n[Bind]:
            if len(PAind) >= len(PBind):
                an.append(an[i]-len(PAind) * len(PBind))
                P[n[Aind]-1].extend(PBind)
                for j in PBind:
                    n[j-1] = n[Aind]
            else:
                an.append(an[i]-len(PAind) * len(PBind))
                P[n[Bind]-1].extend(PAind)
                for j in PAind:
                    n[j-1] = n[Bind]
        else:
            an.append(an[i])
            
        
an = an[::-1]
for k in range(M):
    print(int(an[k]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

def main():
    S = [int(s) for s in input()]
    N = len(S)
    K = 2019

    V = [0] * (N+1)
    count = [0] * 2020
    count[0] = 1
    ans = 0
    ten = 1
    for i in reversed(range(N)):
        rev_i = (N-1)-i
        ten = ten * 10
        v = V[rev_i] + S[i] * ten
        V[rev_i+1] = v
        u = v % K

        count[u] += 1
        cnt = count[u]
        ans -= (cnt-1) * (cnt-2) // 2
        ans += cnt * (cnt-1) // 2


    print(ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def main():
    S = [int(s) for s in input()]
    N = len(S)
    K = 2019

    V = [0] * (N+1)
    for i in reversed(range(N)):
        rev_i = (N-1)-i
        V[rev_i+1] = V[rev_i] + S[i] * (pow(10,rev_i+1,K))
        # print(V)

    dic = {} # value:count
    U = set()
    for v in V:
        u = v % K
        if u in U:
            dic[u] += 1
        else:
            dic[u] = 1
            U.add(u)

    ans = 0
    for u in U:
        u_count = dic[u]
        ans += u_count * (u_count-1) // 2

    # print(S)
    # print(V)
    # print(dic)
    print(ans)

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

def main():
  N,D,A = map(int,input().split())
  import numpy as np
  import math
  XH = [list(map(int,input().split())) for _ in range(N)]
  XH = sorted(XH)
  ans = 0
  l=[0]*N
  x = XH[0][0]
  left = 0
  right = N
  while left+1!=right:
    mid = (right+left)//2
    if XH[mid][0]<=x+2*D:
      left = mid
    else:
      right = mid
  l[0]=left
  for i in range(1,N):
    x = XH[i][0]
    right = N
    left = l[i-1]
    while left+1!=right:
      mid = (right+left)//2
      if XH[mid][0]<=x+2*D:
        left = mid
      else:
        right = mid
    l[i]=left
  H = np.array([xh[1] for xh in XH])
  for i,a in enumerate(l):
    h = H[i]
    if h<=0:
      continue
    else:
      b = math.ceil(h/A)
      ans += b
      H[i:a+1:]-=b*A
  print(ans)
  
main()

### FIXED CODE ###

def main():
  N,D,A = map(int,input().split())
  XH = [list(map(int,input().split())) for _ in range(N)]
  XH = sorted(XH)
  ans = 0
  S = [0]*(N+1)
  x = XH[0][0]
  h = XH[0][1]
  j = 0
  b = (h+A-1)//A
  ans += b
  y = b*A
  while True:
    if j+1>=N:
      break
    if XH[j+1][0]<=x+2*D:
      j+=1
    else:
      break
  S[0]+=y
  S[j+1]-=y
  S[1]+=S[0]
  for i in range(1,N):
    xh = XH[i]
    h = xh[1]
    s = S[i]
    rec = h-s
    if rec<=0:
      S[i+1]+=s
      continue
    else:
      x = xh[0]
      j = max(j,i)
      while True:
        if j+1>=N:
          break
        if XH[j+1][0]<=x+2*D:
          j+=1
        else:
          break
      b = (rec+A-1)//A
      ans += b
      y = b*A
      S[i]+=y
      S[j+1]-=y
      S[i+1]+=s+y
  print(ans)
main()
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

k = int(input())
sum = 0
for i in range(k):
    for j in range(k):
        for m in range(k):
            sum += gcd(i + 1, j + 1, m + 1)
print(sum)



### FIXED CODE ###

from math import gcd

k = int(input())
sum = 0
for i in range(1, k + 1):
    for j in range(1, k + 1):
        for m in range(1, k + 1):
            sum += gcd(gcd(i, j), m)
print(sum)
### BUGGY CODE ###

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

x = 1
for i in range(n):
    x *= a[i]    
    
if x > 1000000000000000000:
    if 0 in a:
        print(0)
    else:
        print(-1)
else:
    print(x)


### FIXED CODE ###

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

x = 1
flag = False
INF = 10**18
if 0 in a:
    print(0)
else:
    for i in range(n):
        if flag == False:
            x *= a[i]
        if x > INF:
            flag = True
    
    if flag:
        print(-1)
    else:
        print(x)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

N, M, K = map(int, input().split())

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

total = 0

stack = [(0, 0, 0, 0, 0)]
res = 0
flg = 0
while stack:
    av, ai, bv, bi, ans = stack.pop()
    if av + bv > K:
        res = max(res, ans-1)
        flg = 1
        continue
    if ai <= len(A) - 1:
        stack.append((av+A[ai], ai+1, bv, bi, ans+1))
        # print((av+A[ai], ai+1, bv, bi, ans+1))
    if bi <= len(B) - 1:
        stack.append((av, ai, bv+B[bi], bi+1, ans+1))
        # print((av+A[ai], ai+1, bv, bi, ans+1))

if flg:
    print(res)
else:
    print(ans)    


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

N, M, K = map(int, input().split())

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

a = [0] + A
b = [0] + B

for i in range(len(a)-1):
    a[i+1] += a[i]

for i in range(len(b)-1):
    b[i+1] += b[i]

ans = 0
j = M

for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [float('inf')]*N
dp[0] = 0
for i in range(1,N):
    for j in range(K):
        if i+j > N-1:
            break
        dp[i+j] = min(dp[i-1]+abs(h[i-1]-h[i+j]),dp[i+j])
print(dp[-1])

### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [float('inf')]*(N+K)
dp[0] = 0
for i in range(N):
    for j in range(K+1):
        try:
            dp[i+j] = min(dp[i]+abs(h[i]-h[i+j]),dp[i+j])
        except Exception:
            break
print(dp[N-1])
### BUGGY CODE ###

n = int(input())

lst = [-1 for i in range(n)]
print(0)
sex0 = input()
if sex0 == 'Male':
    lst[0] = 1
    leftsex = 1
elif sex0 == 'Female':
    lst[0] = 0
    leftsex = 0
else:
    exit()

print(n-1)
sexn_1 = input()
if sexn_1 == 'Male':
    lst[n-1] = 1
    rightsex = 1
elif sexn_1 == 'Female':
    lst[n-1] = 0
    rightsex = 0
else:
    exit()

left = 0
right = n-1
while left+1 < right:
    mid = (left+right)//2
    print(mid)
    sexmid = input()
    if sexmid == 'Male':
        lst[mid] = 1
        midsex = 1
    elif sexmid == 'Female':
        lst[mid] = 0
        midsex = 0
    else:
        exit()
    
    if (mid-left) % 2 == midsex - leftsex:
        left = mid
    else:
        right = mid

### FIXED CODE ###

n = int(input())

lst = [-1 for i in range(n)]
print(0)
sex0 = input()
if sex0 == 'Male':
    lst[0] = 1
    leftsex = 1
elif sex0 == 'Female':
    lst[0] = 0
    leftsex = 0
else:
    exit()

print(n-1)
sexn_1 = input()
if sexn_1 == 'Male':
    lst[n-1] = 1
    rightsex = 1
elif sexn_1 == 'Female':
    lst[n-1] = 0
    rightsex = 0
else:
    exit()

left = 0
right = n-1
while left+1 < right:
    mid = (left+right)//2
    print(mid)
    sexmid = input()
    if sexmid == 'Male':
        lst[mid] = 1
        midsex = 1
    elif sexmid == 'Female':
        lst[mid] = 0
        midsex = 0
    else:
        exit()
    
    if (mid-left) % 2 == abs(midsex-leftsex):
        left = mid
        leftsex = midsex
    else:
        right = mid
        rightsex = midsex
### BUGGY CODE ###

#!/usr/bin/env python3
N = int(input())
X = input()

x_num = int(X, 2)
cnt1 = X.count('1')


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


def f1(x):
    cnt = 0
    while (x > 0):
        x %= bin(x).count('1')
        cnt += 1
    return cnt


for i, x in enumerate(list(X)):
    if (x == '1'):
        #x_num = int(''.join(X), 2)
        if (x_num - (2**(N-(i+1)))) != 0:
            print(f1((x_num - (2 ** (N - (i + 1)))) % (cnt1 - 1)) + 1)
        else:
            print(0)
    else:
        #x_num = int(''.join(X), 2)
        print(f1((x_num + (2 ** (N - (i + 1)))) % (cnt1 + 1)) + 1)

### FIXED CODE ###

#!/usr/bin/env python3
N = int(input())
X = input()

x_num = int(X, 2)
cnt1 = X.count('1')

p_zero = x_num % (cnt1 + 1)
p_one = (x_num % (cnt1 - 1) if cnt1 - 1 > 0 else 1)


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


def f1(x):
    cnt = 0
    while (x > 0):
        x %= bin(x).count('1')
        cnt += 1
    return cnt


for i, x in enumerate(list(X)):
    if (x == '1'):
        #x_num = int(''.join(X), 2)
        if cnt1 - 1 > 0:
            xxx = (p_one - pow(2, (N - (i + 1)), cnt1 - 1)) % (cnt1 - 1)
            xxx += cnt1 - 1 if xxx < 0 else 0
            print(f1(xxx) + 1)
        else:
            print(0)
    else:
        #x_num = int(''.join(X), 2)
        xxx = (p_zero + pow(2, (N - (i + 1)), cnt1 + 1)) % (cnt1 + 1)
        xxx += cnt1 + 1 if xxx < 0 else 0
        print(f1(xxx) + 1)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

def root(x):
    if uf[x] == x:
        return x
    else:
        uf[x] = root(uf[x])
        return uf[x]

def same(x, y):
    return root(x) == root(y)

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    uf[rx] = ry

N, M = map(int,readline().split())
p = list(map(int,readline().split()))
p.insert(0, -1)
uf = [i for i in range(N+1)]
for i in range(M):
    a, b = (map(int,readline().split()))
    unite(a, b)
for i in range(1, N+1):
    root(i)

ans = 0
match = [[] for i in range(N+1)]
for i in range(1, N+1):
    match[uf[i]].append(i)
for i in range(1, N+1):
    matchlen = len(match[i])
    for j in range(matchlen):
        if p[match[i][j]] in match[i]:
            ans += 1
print(str(ans))

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def root(x):
    if uf[x] == x:
        return x
    else:
        uf[x] = root(uf[x])
        return uf[x]

def same(x, y):
    return root(x) == root(y)

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    uf[rx] = ry

N, M = map(int,readline().split())
p = list(map(int,readline().split()))
p.insert(0, -1)
uf = [i for i in range(N+1)]
for i in range(M):
    a, b = (map(int,readline().split()))
    unite(a, b)
for i in range(1, N+1):
    root(i)

ans = 0
#N += 1
#match = [[] for i in range(N)]
#for i in range(1, N):
#    match[uf[i]].append(i)
#for i in range(1, N):
#    matchlen = len(match[i])
#    for j in range(matchlen):
#        if p[match[i][j]] in match[i]:
#            ans += 1

for i in range(1, N+1):
    if same(i, p[i]):
        ans += 1
print(str(ans))
### BUGGY CODE ###

from collections import defaultdict

n = int(input())
s = input()
passwords = defaultdict(int)
for i in range(1000):
    password = "0" * (3 - len(str(i))) + str(i)
    for j in range(n):
        if s[j] == password[0]:
            #print("OK1", password)
            for k in range(j + 1, n):
                if s[k] == password[1]:
                    #print("OK2")
                    for l in range(k + 1, n):
                        if s[l] == password[2]:
                            #print("OK3", password)
                            passwords[password] += 1
                            break


print(len(passwords))

### FIXED CODE ###

N = int(input())
S = input()

ans = 0
for i in range(1000):
    num = str(i).zfill(3)
    if S.find(num[0]) == -1:
        continue
    S1 = S[S.find(num[0]) + 1:]
    if S1.find(num[1]) == -1:
        continue
    S2 = S1[S1.find(num[1]) + 1:]
    if S2.find(num[2]) == -1:
        continue
    ans += 1

print(ans)
### BUGGY CODE ###

N,K,Q,*A = map(int, open(0).read().split())
ans = [K] * N

for a in A:
    ans[a-1] += 1
    ans = [x-1 for x in ans]

for x in ans:
    print('Yes' if x > 0 else 'No')

### FIXED CODE ###

N,K,Q,*A = map(int, open(0).read().split())
ans = [K] * N

for a in A:
    ans[a-1] += 1

for x in ans:
    y = x - Q
    print('Yes' if y > 0 else 'No')
### BUGGY CODE ###

s = input()
table = [0 for i in range(2019)]
table[0] = 1
num = 0
d = 1
for c in s[::-1]:
    num += (int(c) * d)
    num %= 2019
    d *= 10
    table[num] += 1

ans = 0
for cnt in table:
    ans += cnt * (cnt - 1) // 2

print(ans)

### FIXED CODE ###

s = input()
table = [0 for i in range(2019)]
table[0] = 1
num = 0
d = 1
for c in s[::-1]:
    num += (int(c) * d)
    num %= 2019
    d *= 10
    d %= 2019
    table[num] += 1

ans = 0
for cnt in table:
    ans += cnt * (cnt - 1) // 2

print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

import numpy as np

N = int(input())
P = list(map(int,input().split()))

if 0 in P:
    print(0)
    exit()

ans=1
P.sort(reverse=True)

for i in range(N):
    ans*=P[i]
    if ans>10**18:
        print(-1)
        exit()

print(ans)
### BUGGY CODE ###

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

dup = sum(a) - n * (n + 1) // 2
d1 = a.index(dup)
d2 = a.index(dup, d1 + 1)

N = n + 1
Ndup = d1 + n - d2

MOD = 10 ** 9 + 7

# パスカルの三角形
def makePascal(N):
    C = [0 for i in range(N // 2 + 1)]
    C[0] = 1
    for i in range(N):
        for j in range(len(C) - 1, 0, -1):
            C[j] = (C[j] + C[j - 1]) % MOD
    return C

Pascal = {}
Pascal[N] = makePascal(N)
Pascal[Ndup] = makePascal(Ndup)

def comb(n, r):
    if r < len(Pascal[n]):
        return Pascal[n][r]
    elif r <= n:
        return Pascal[n][n - r]
    else:
        return 0

for k in range(1, N + 1):
    C = comb(N, k)
    Cdup = comb(Ndup, k - 1)
    print((C - Cdup) % MOD)


### FIXED CODE ###

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

dup = sum(a) - n * (n + 1) // 2
d1 = a.index(dup)
d2 = a.index(dup, d1 + 1)

N = n + 1
Ndup = d1 + n - d2

MOD = 10 ** 9 + 7

def power(x, n):
    ans = 1
    while n:
        if n % 2 == 1:
            ans = (ans * x) % MOD
        x = (x * x) % MOD
        n //= 2
    return ans

# fack[k]: kの階乗
fact = [0 for i in range(N + 1)]
fact[0] = 1
for i in range(1, N + 1):
    fact[i] = (fact[i - 1] * i) % MOD

# inv[k]: kの階乗の逆元
inv = [0 for i in range(N + 1)]
inv[N] = power(fact[N], MOD - 2) % MOD
for i in range(N - 1, -1, -1):
    inv[i] = (inv[i + 1] * (i + 1)) % MOD

def comb(n, r):
    if n < r:
        return 0
    else:
        return (fact[n] * inv[n - r] * inv[r]) % MOD

for k in range(1, N + 1):
    C = comb(N, k)
    Cdup = comb(Ndup, k - 1)
    print((C - Cdup) % MOD)
### BUGGY CODE ###

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
  for k in range(i+1):
    if i+j-k<=N:
      res+=Factorial[N]*inverseFactorial[i-k]*inverseFactorial[j-k]*inverseFactorial[k]*inverseFactorial[N-i-j+k]
  return res%mod
      
ans=0  
for i in range(K//A+1):
  if (K-A*i)%B==0:
    j=(K-A*i)//B
    ans+=f(i,j)
    ans%=mod
    
print(ans)

  

### FIXED CODE ###

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 comb(x,y):
  if x<y:
    return 0
  return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod
      
ans=0  
for i in range(K//A+1):
  if (K-A*i)%B==0:
    j=(K-A*i)//B
    ans+=comb(N,i)*comb(N,j)
    ans%=mod
  

    
print(ans%mod)