Harryxun/stf_run huggingface dataset:
import collections
N, M, K = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]

CD = [tuple(map(int, input().split())) for i in range(K)]


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return


# F = [set() for i in range(N)]
F = unionFind(N)
f = [set() for i in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    f[a].add(b)
    f[b].add(a)
    F.unite(a+1, b+1)

B = [set() for i in range(N)]
for c, d in CD:
    c -= 1
    d -= 1
    B[c].add(d)
    B[d].add(c)

ans = [0]*N
D = collections.defaultdict(set)
for i in range(N):
    D[F.root(i)].add(i)

# print(f)
for i in range(N):
    x = D[F.root(i)]
    ret = len(x)
    ret -= 1
    ret -= len(x & f[i])
    ret -= len(x & B[i])
    ans[i] = ret

print(*ans)


### FIXED CODE ###


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)


class unionFind:
    parent = []
    count = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.count = [1 for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.count[y] += self.count[x]
            self.count[x] = self.count[y]
            return

    def getCount(self, x):
        self.count[x] = self.count[self.root(x)]
        return(self.count[x])


N, M, K = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]

CD = [tuple(map(int, input().split())) for i in range(K)]

G = unionFind(N)
for a, b in AB:
    G.unite(a, b)

for i in range(N):
    G.root(i)

ans = [G.getCount(i) - 1 for i in range(N)]
# print(ans)
# print(G.count)
for a, b in AB:
    ans[a-1] -= 1
    ans[b-1] -= 1

for c, d in CD:
    if G.same(c, d):
        ans[c-1] -= 1
        ans[d-1] -= 1

print(*ans)
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
po = sorted([ai for ai in a if ai > 0], reverse=True)
ne = sorted(ai for ai in a if ai < 0)
ze = 0 in a
mod = 10**9 + 7
c = 1
if len(po) == 0 or len(po) + len(ne) // 2 * 2 < k:
    if ze:
        print(0)
    else:
        for bi in sorted(po + ne, key=abs)[:k]:
            c = c * bi % mod
        print(c)
elif len(ne) < 2:
    for ai in sorted(a, reverse=True)[:k]:
        c = c * ai % mod
    print(c)
else:
    if len(po) >= k:
        pi = k - 1
        ni = -1
        pc = po[:k]
        nc = []
    else:
        if (k - len(po)) % 2:
            pi = len(po) - 2
            pc = po[:-1]
        else:
            pi = len(po) - 1
            pc = po
        ni = k - len(pc) - 1
        nc = ne[:k - len(pc)]
    for _ in range(len(pc) // 2):
        if ne[ni + 1] * ne[ni + 2] < po[pi - 1] * po[pi - 2]:
            break
        nc = nc + ne[ni + 1:ni + 3]
        pc = pc [:-2]
        ni += 2
        pi -= 2
    for pp in pc:
        c = c * pp % mod
    for nn in nc:
        c = c * nn % mod
    print(c)


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    mod = 10**9 + 7
    p = 1
    if n == k:
        for ai in a:
            p = p * ai % mod
        print(p)
        return
    if a[0] < 0 and k % 2:
        for ai in a[:k]:
            p = p * ai % mod
        print(p)
        return
    b = sorted([(abs(ai), ai) for ai in a], reverse=True)
    s = 0
    for ba, bb in b[:k]:
        p = p * ba % mod
        if bb < 0:
            s += 1
    if s % 2 == 0:
        print(p)
        return
    pa, na, pb, nb = [-1] * 4
    for ba, bb in b[:k]:
        if bb < 0:
            na = ba
        else:
            pa = ba
    for ba, bb in b[k:][::-1]:
        if bb < 0:
            nb = ba
        else:
            pb = ba
    if pa == -1 or nb == -1:
        print(p * pb * pow(na, mod - 2, mod) % mod)
    elif pb == -1 or na == -1:
        print(p * nb * pow(pa, mod - 2, mod) % mod)
    elif pa * pb > na * nb:
        print(p * pb * pow(na, mod - 2, mod) % mod)
    else:
        print(p * nb * pow(pa, mod - 2, mod) % mod)


if __name__ == '__main__':
    main()
int main(void) {
    int m,f,r;
    scanf("%d %d %d",&m,&f,&r);
    while(m!=-1 || f!=-1 || r!=-1) {
        if(m==-1 || f==-1)printf("F\n");
        else if(m+f>=80)printf("A\n");
        else if(m+f>=65)printf("B\n");
        else if(m+f>=50)printf("C\n");
        else if(m+f>=30) {
            if(r>=50)printf("C\n");
            else printf("D\n");
        }
        else printf("F\n");
        scanf("%d %d %d",&m,&f,&r);
    }
    return 0;
}

### FIXED CODE ###

import sys
 
for line in sys.stdin:
    m, f, r = map(int, line.split())
    if m == f == r == -1:
        break
    if m == -1 or f == -1:
        print('F')
    elif (m + f) >= 80:
        print('A')
    elif (m + f) >= 65:
        print('B')
    elif (m + f) >= 50:
        print('C')
    elif (m + f) >= 30:
        if r >= 50:
            print('C')
        else:
            print('D')
    else:
        print('F')
x,a,b=map(int,input().split())
disA=abs(x-a)
disB=abs(x-b)
if disA>disB:
  print(B)
else:
  print(A)

### FIXED CODE ###

x,a,b=map(int,input().split())
disA=abs(x-a)
disB=abs(x-b)
if disA>disB:
  print('B')
else:
  print('A')
import sympy

n = int(input())

ans = 0
for i in range(1, n + 1, 2):
    if len(sympy.divisors(i)) == 8:
        ans += 1

print(ans)

### FIXED CODE ###

def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


n = int(input())

ans = 0
for i in [2 * x + 1 for x in range((n + 1) // 2)]:
    if len(make_divisors(i)) == 8:
        ans += 1

print(ans)
import bisect
 
N, M = map(int, input().split())
A = list(map(int, input().split()))
 
def cnt(a, m):
  cnt_tmp = 0
  for aa in a:
    bi = bisect.bisect_left(a, m - aa)
    #print(a, m, m - aa, bi)
    cnt_tmp += N - bi
  return cnt_tmp
 
A.sort()
 
l = 0
r = 10**10
 
while l+1<r:
  mid = (l + r) // 2
  cnt_loop1 = cnt(A, mid)
  #cnt_loop2 = cnt(A, mid+1)
  #print(mid, cnt_loop1, cnt_loop2)
  
  if cnt_loop1 >= M and cnt_loop2 < M:
    break
  if cnt_loop1 >= M:
    l = mid
  else:
    r = mid
#print(mid, cnt_loop1, cnt_loop2)
 
S = [0] * (N+1)
for i in range(1, N+1):
  S[i] = S[i-1]+A[i-1]
#print(S[N])
 
answer = 0
for aa in A:
  bi = bisect.bisect_left(A, mid - aa)
  answer += S[N] - S[bi] + (N - bi) * aa
print(answer-(cnt_loop1-M)*mid)

### FIXED CODE ###

from bisect import bisect_left

N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort()
left = 0
right = max(A) * 2 + 1

while left + 1 < right:
  mid = (left + right) // 2
  
  cnt = 0
  for i in range(N):
    cnt += N - bisect_left(A, mid - A[i])
  if cnt >= M:
    left = mid
  else:
    right = mid

Acum = [0]
for a in A:
  Acum.append(Acum[-1] + a)

answer = 0
cnt = 0
for i in range(N):
  bi = bisect_left(A, left - A[i])
  answer += (Acum[-1] - Acum[bi]) + (N - bi) * A[i]
  cnt += (N - bi)
answer -= (cnt - M) * left

print(answer)
s = input()
t = input()
\\print(t[:len(s)])
if s == t[:len(s)]:
  print("Yes")
else :
  print("No")



### FIXED CODE ###

s = input()
t = input()

if s == t[:len(s)]:
  print("Yes")
else :
  print("No")
n = int(input())
a = list(map(int, input().split()))

if n == 1:
  print(1)
else:
  ans = 0
  for i in range(1, max(a)):
    res = a.count(i) + a.count(i+1) + a.count(i-1)
    ans = max(ans, res)
    
  print(ans

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
ans = 0
for x in range(min(a), max(a)+1):
  res = c[x] + c[x+1] + c[x-1]
  ans = max(ans, res)
print(ans)
import sys
from heapq import*
def g(s,g):
 F=[1e7]*-~n;F[s]=0
 H=[(0,s)]
 while H:
  c,u=heappop(H)
  if u==g:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:
    F[v]=t
    heappush(H,(t,v))
 return-1
for e in iter(input,'0 0'):
 n,k=map(int,e.split())
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=input()
  if f[0]:
   c,d,e=map(int,f[2:].split())
   E[c]+=[(e,d)];E[d]+=[(e,c)]
  else:print(g(map(int,f[2:].split())))


### FIXED CODE ###

def s():
 import sys
 r=sys.stdin.readline
 I=float('inf')
 for e in iter(r,'0 0\n'):
  n,k=map(int,e.split())
  F=[[I]*-~n for _ in[0]*-~n]
  for i in range(1,n+1):F[i][i]=0
  for _ in[0]*k:
   f=r();g=map(int,f[2:].split())
   if'0'==f[0]:a,b=g;A=F[a][b];print([A,-1][A==I])
   else:
    c,d,e=g
    if e<F[c][d]:
     for i in range(2,n+1):
      for j in range(1,i):
       F[i][j]=F[j][i]=min(F[i][j],F[i][c]+e+F[d][j],F[i][d]+e+F[c][j])
s()
a,b = map(int,input().split())
     
    t = b//1000
     
    f = False
     
    for i in range(t//10+1):
        for j in range((t-i*10)//5+1):
            if a == t - i*9 - j*4 and t == i*10+j*5+(a-i-j) and a-i-j>=0:
                f = True
                break
        if f:
            break
     
    if f:
        print(i,j,a-i-j)
    else:
        print(-1,-1,-1)

### FIXED CODE ###

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

t = b//1000

f = False

for i in range(t//10+1):
    for j in range((t-i*10)//5+1):
        if a == t - i*9 - j*4 and b == i*10000+j*5000+(a-i-j)*1000 and a-i-j>=0:
            f = True
            break
    if f:
        break

if f:
    print(i,j,a-i-j)
else:
    print(-1,-1,-1)
import sys

A = input()
B = input()

if A = 1:
    if B = 2:
        print(3)
    else:
        print(2)
elif A = 2:
    if B = 1:
        print(3)
    else:
        print(1)
elif A = 3:
    if B = 1:
        print(2)
    else:
        print(1)


### FIXED CODE ###

import sys

A = input()
B = input()

if A == '1':
    if B == '2':
        print('3')
    else:
        print('2')
elif A == '2':
    if B == '1':
        print('3')
    else:
        print('1')
elif A == '3':
    if B == '1':
        print('2')
    else:
        print('1')
,M=map(int,input().split())
L=list(map(int,input().split()))
for i in range(M):
  X=X+L[i]
if N-X<0:
  print(-1)
else:
  print(N-X)

### FIXED CODE ###

N,M=map(int,input().split())
L=list(map(int,input().split()))
X=0
for i in range(M):
  X=X+L[i]
if N-X<0:
  print(-1)
else:
  print(N-X)
import statistics
import math
N = int(input())
AS = input().split()
AS = [int(i) for i in AS]
BS = [int(AS[j-1] - j) for  i in range(1,N+1)]
b = int('{0:8.0f}'.format(statistics.median(BS)))
result_a = 0
result_b = 0
result_c = 0
for j in range (1, N+1):
    result_a += abs(int(AS[j-1]) - b - j)
for j in range (1, N+1):
    result_b += abs(int(AS[j-1]) - b - 1 - j)
for j in range (1, N+1):
    result_c += abs(int(AS[j-1]) - b + 1 - j)
print (min(result_a,result_b,result_c))

### FIXED CODE ###

N = int(input())
AS = input().split()
AS = [int(i) for i in AS]
BS = [int(AS[j-1] - j) for j in range(1,N+1)]
BS_s = BS.sort()
b = BS[N//2]
result_a = 0
result_b = 0
result_c = 0
for j in range (1, N+1):
    result_a += abs(int(AS[j-1]) - b - j)
for j in range (1, N+1):
    result_b += abs(int(AS[j-1]) - b - 1 - j)
for j in range (1, N+1):
    result_c += abs(int(AS[j-1]) - b + 1 - j)
print (int(min(result_a,result_b,result_c)))
N = int(input())
ls = list(map(int, input().split())
counter = 1
for elem in ls:
    if elem == counter:
        counter += 1
print(N - counter)

### FIXED CODE ###

N = int(input())
ls = list(map(int, input().split()))
counter = 1
for elem in ls:
    if elem == counter:
        counter += 1
if counter == 1:
    print(-1)
else:
    print(N - counter + 1)
n = int(input())
v = [int(i) for i in input().split()]
v.sort()
ans = v[0]
for i in range(1, len(v)):
    ans = (ans + v[i]) / 2
print(ans)


### FIXED CODE ###

a = int(input())
s = input()
if a >= 3200:
    print(s)
else:
    print("red")
N = int(input())
a = [[] for _ in range(N)]
ans = [0]*N
for _ in range(N-1):
  u, v, w = map(int, input().split())
  a[u-1].append([v-1, w])
  a[v-1].append([u-1, w])
def calc(u, b):
  for v, w in a[u]:
    if not b == v:
      ans[v]=(ans[u] + w)%2
      calc(v, u)
calc(0, -1)
for i in ans:
  if i % 2 == 0:
    print(0)
  else:
    print(1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
N = int(input())
a = [[] for _ in range(N)]
ans = [0]*N
for _ in range(N-1):
  u, v, w = map(int, input().split())
  a[u-1].append([v-1, w])
  a[v-1].append([u-1, w])
def calc(u, b):
  for v, w in a[u]:
    if not b == v:
      ans[v]=(ans[u] + w)%2
      calc(v, u)
calc(0, -1)
for i in ans:
  if i % 2 == 0:
    print(0)
  else:
    print(1)
def main():
    import sys
    in = sys.stdin.buffer.readline
    ini = lambda: int(ns())
    ina = lambda: list(map(int, in().split()))
    ins = lambda: in().strip()
    
    n= ini()
    tmp = 0
    for _ in range(n):
        l,r = ina()
        if(l==r):
            tmp+=1
            if(tmp==3):
                print("Yes")
                return
        else:
            tmp =0
        


        


    




















if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import sys
    ikimasu = sys.stdin.buffer.readline
    ini = lambda: int(ins())
    ina = lambda: list(map(int, ikimasu().split()))
    ins = lambda: ikimasu().strip()
    
    n= ini()
    tmp = 0
    for _ in range(n):
        l,r = ina()
        if(l==r):
            tmp+=1
            if(tmp==3):
                print("Yes")
                return
        else:
            tmp =0
    print("No")
        


        


    




















if __name__ == "__main__":
    main()
n,y = map(int,input().split())

for a in range(n+1):
  for b in range(n+1-a):
    c=n-a-b
    if y==a*10000+b*5000+c*1000 and n==a+b+c:
      i=a
      j=b
      k=c
      
      break
      
print(i,j,k)

    
    


### FIXED CODE ###

n,y = map(int,input().split())
l=0
for a in range(n+1):
  for b in range(n+1-a):
    c=n-a-b
    if y==a*10000+b*5000+c*1000 and n==a+b+c:
      i=a
      j=b
      k=c
      
      l=1
      break

if l==1:
  print(i,j,k)
else:
  print(-1,-1,-1)
S=input()
counter
for i in len(S):
    if S[i] == '+':
        counter += 1
    else:
        counter -= 1

print(counter)

### FIXED CODE ###

S=list(input())
counter = 0
for i in range(len(S)):
    if S[i] == '+':
        counter += 1
    elif S[i] == '-':
        counter -= 1

print(counter)
N , L= map(int,input().split())
lst = list()
lst2 = ''
for i in range(L):
    lst.append(input())
lst.sort()
#for k  in range(N):
#    for j in range(N-1):
#        if lst[j] > lst[j+1]:
#            lst[j],lst[j+1] = lst[j+1] ,lst[j]

for i in lst:
    lst2 += i
print(lst2)


### FIXED CODE ###

N,L=map(int, input().split())
S=[]
for i in range(N):
    S.append(input())
S.sort()
result=''
for j in range(N):
    result+=S[j]     
print(result)
S = list(input())
K = int(input())

inter = 0
inner = 0

for i in range(len(S) - 1):
    if S[i] == S[i + 1]:
        S[i + 1] = '#' + S[i + 1]
        inner += 1
if S[0] == S[-1]:
    if S[-2] == '#' + S[-1]:
        pass
    else:
        inter += K - 1
# print(S)
# print(inter)
print(inter + inner * K)

### FIXED CODE ###

S = input()
K = int(input())



def func(S):
    inner = 0
    S = list(S)
    for i in range(len(S) - 1):
        if S[i] == S[i + 1]:
            S[i + 1] = '#'
            inner += 1
    return inner

if len(set(list(S))) == 1:
    print(len(S) * K // 2)
else:
    inner = func(S)
    inter = func(S * 2) - func(S) * 2
    print(inner * K + inter * (K - 1))
class DFS:
    def __init__(self,n,a,b,c,d):
        self.N = n
        self.A = a
        self.B = b
        self.C = c
        self.D = d
        self.ans = self.N * self.D
        self.Q = deque([[n,0]])
    def dfs(self):
        while self.Q:
            num,cost = self.Q.popleft()
            if num == 0:
                self.ans = min(self.ans, cost)
            elif num == 1:
                self.ans = min(self.ans, cost + self.D * num)
            else:
                # 5の倍数に下げて5で割った場合
                temp_num = num//5
                temp_cost = cost + (num - (num//5)*5) * self.D + self.C
                self.Q.appendleft([temp_num,temp_cost])
                
                # 3の倍数に下げて3で割った場合
                temp_num = num//3
                temp_cost = cost + (num - (num//3)*3) * self.D + self.B
                self.Q.appendleft([temp_num,temp_cost])
                
                # 2の倍数に下げて2で割った場合
                temp_num = num//2
                temp_cost = cost + (num - (num//2)*2) * self.D + self.A
                self.Q.appendleft([temp_num,temp_cost])
                
                # 全て引いた場合
                self.ans = min(self.ans, num*self.D + cost)
                
        return self.ans
T = int(input())
for _ in range(T):
    N,A,B,C,D = map(int,input().split())
    case = DFS(N,A,B,C,D)
    print(case.dfs())


### FIXED CODE ###

from collections import defaultdict,deque
class dfs:
    def __init__(self,n,a,b,c,d):
        self.N = n
        self.A = a
        self.B = b
        self.C = c
        self.D = d
        self.ans = self.N * self.D
        self.memory = defaultdict(int)
        self.Q = deque([[self.N,0]])
    def dfs(self):
        while self.Q:
            num,cost = self.Q.popleft()
            if self.memory[num] > cost :
                pass
            else:
                if num == 0:
                    self.ans = min(self.ans,cost)
                elif num == 1:
                    self.ans = min(self.ans,cost+self.D)
                else:
                    for step,a_cost in [[2,self.A],[3,self.B],[5,self.C]]:
                        if num % step != 0:
                            temp_num = (num//step)+1
                            temp_cost = cost + (((num//step)+1)*step - num) * self.D + a_cost
                            self.memo_check_append(temp_num,temp_cost)
                        temp_num = num//step
                        temp_cost = cost + (num - (num//step)*step) * self.D + a_cost
                        self.memo_check_append(temp_num,temp_cost)
                    self.ans = min(self.ans,cost + num * self.D)
        return self.ans
    def memo_check_append(self,n,c):
        if self.memory[n] > c or self.memory[n] == 0:
            self.Q.append([n,c])
            self.memory[n] = c

N = int(input())
for _ in range(N):
  N,A,B,C,D = map(int,input().split())
  T = dfs(N,A,B,C,D)
  print(T.dfs())
import math
N = int(input())
Alist = list(map(int, input().split()))
def gcds(numbers):
    if len(numbers) == 2:
        return math.gcd(*numbers)
    else:
        n1 = math.gcd(numbers[0], numbers[1])
        return gcds(* [n1]+numbers[2:])
if len(Alist)>2:
    gcdlist = [gcds(Alist[:i]+Alist[i+1:]) for i in range(N)]
    print(max(gcdlist))
else:
    gcds(Alist)

### FIXED CODE ###

from fractions import gcd
N = int(input())
Alist = [0]+list(map(int, input().split()))+[0]
Rlist = [0]*(N+2)
Llist = [0]*(N+1)
for i in range(N):
    Llist[i+1] = gcd(Llist[i], Alist[i])
    Rlist[N-i] = gcd(Rlist[N-i+1], Alist[N-i+1])
print(max([gcd(Rlist[i], Llist[i]) for i in range(1,N+1)]))
# -*- coding: utf-8 -*-
from scipy.special import comb

N = int(input())
s = [input() for i in range(N)]

for i in range(N):
    s[i] = ''.join(sorted(s[i]))

unique_s = set(s)

output = 0
for k in unique_s:
     if s.count(k) != 1:
        output += int(comb(s.count(k), 2))

print(output)

### FIXED CODE ###

# -*- coding: utf-8 -*-

N = int(input())
s = [input() for i in range(N)]

output = 0
dic = dict()
for i in range(N):
    tmp = ''.join(sorted(s[i]))
    if tmp not in dic:
        dic[tmp] = 1
    else:
        output += dic[tmp]
        dic[tmp] += 1

print(output)
N = int((input())

if N % 2 == 0:
  print(N / 2)
else:
  print(N // 2 + 1)


### FIXED CODE ###

UNKO = int(input())
print(UNKO // 2 + UNKO % 2)
s=input()
t=input()

dp=[[-1]*(3001) for x in range(3001)]
arr = ""
def func(i,j):
    if i>=(len(s)-1) or j>=(len(t)-1):
        return 0
    if dp[i][j]!=-1:
        return dp[i][j]
    if s[i]==t[j]:
        dp[i][j] = func(i+1,j+1)+1
        return dp[i][j]
    if s[i]!=t[j]:
        dp[i][j] = max(func(i+1,j),func(i,j+1))
        return dp[i][j]
l=func(0,0)
i,j=0,0
while len(arr)<l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)

### FIXED CODE ###

s=input()
t=input()

dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""
for i in range(len(s),-1,-1):
    for j in range(len(t),-1,-1):
        if i>=(len(s)) or j>=(len(t)):
            dp[i][j] = 0
        else:
            if s[i] == t[j]:
                dp[i][j] = dp[i+1][j+1] + 1
            else:
                dp[i][j] = max(dp[i+1][j],dp[i][j+1])

l=dp[0][0]
i,j=0,0
while len(arr)!=l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>=dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)



# def func(i,j):
    # if i>=(len(s)) or j>=(len(t)):
    #     return 0
    # if dp[i][j]!=-1:
    #     return dp[i][j]
    # if s[i]==t[j]:
    #     dp[i][j] = func(i+1,j+1)+1
    #     return dp[i][j]
    # if s[i]!=t[j]:
    #     dp[i][j] = max(func(i+1,j),func(i,j+1))
    #     return dp[i][j]
# l=func(0,0)
import itertools
import math
n, a, b, k = map(int, input().split())
count = 0
for i in range(math.floor(k/a)):
    if (k - (i * a)) % b == 0:
        count += (itertools.combinations(n, i) * itertools.combinations(n, (k-i*a)/b))
print(count%998244353)

### FIXED 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)