Harryxun/stf_run huggingface dataset:
def create_edge(fr,to,weight,si):
    edges = []
    if si == '-':
        edges.append((fr,to,weight))
        edges.append((to,fr,0))
    else:
        edges.append((to,fr,-weight))
    return edges

#????????????????????´???-1?????????
def bellmanford(edges, length):
    start_vertex = 0
    
    distance = [float('inf')] * length
    distance[start_vertex] = 0
    
    for i in range(length):
        for fr, to, weight in edges:
            if distance[to] > distance[fr] + weight:
                distance[to] = distance[fr] + weight

    for fr, to, weight in edges:
        if distance[to] > distance[fr] + weight:
           return -1
    return max(distance)

import sys
import re
import math

n,c = map(int, f.readline().split())

p = re.compile('(\d+)(\D+)(\d+)(\D+)(\d+)')
constraints = [p.match(line).groups() for line in f]

fixed_edges = []
floating_edges = []
for ai, oi, bi, si, di in constraints:
    fr,to,weight = int(ai) - 1,int(bi) - 1,int(di)

    if oi == '*':
        floating_edges.append((create_edge(fr,to,weight,si),create_edge(to,fr,weight,si)))
    else:
        if oi == '>=':
            fr, to = to, fr
        fixed_edges.extend(create_edge(fr,to,weight,si))

distance = []
for edges in itertools.product(*floating_edges):
    distance.append(bellmanford(fixed_edges + [y for x in edges for y in x], n))

print(max(distance))

### FIXED CODE ###

import sys
import re
import math
import itertools
def create_edge(fr,to,weight,si):
    edges = []
    if si == '-':
        edges.append((fr,to,weight if to else 0))
        edges.append((to,fr,0))
    else:
        edges.append((to,fr,-weight))
    return edges
#????????????????????´???-1?????????
def bellmanford(edges, length):
    start_vertex = 0
    
    distance = [float('inf')] * length
    distance[start_vertex] = 0
    
    for i in range(length):
        for fr, to, weight in edges:
            if distance[to] > distance[fr] + weight:
                distance[to] = distance[fr] + weight

    for fr, to, weight in edges:
        if distance[to] > distance[fr] + weight:
           return -1
    if min(distance[1:]) < 0:
        return -1
    return max(distance)
f = sys.stdin


n,c = map(int, f.readline().split())

p = re.compile('(\d+)(\D+)(\d+)(\D+)(\d+)')
constraints = [p.match(line).groups() for line in f]

fixed_edges = []
floating_edges = []
for ai, oi, bi, si, di in constraints:
    fr,to,weight = int(ai) - 1,int(bi) - 1,int(di)

    if oi == '*':
        if fr and to:
            floating_edges.append((create_edge(fr,to,weight,si),create_edge(to,fr,weight,si)))
            continue
        oi = '<=' if fr < to else '>='

    if oi == '>=':
        fr, to = to, fr
    
    fixed_edges.extend(create_edge(fr,to,weight,si))
distance = []
for edges in itertools.product(*floating_edges):
    distance.append(bellmanford(fixed_edges + [y for x in edges for y in x], n))
print(max(distance))
A = []
A += input().split()
A += input().split()
A+= input().split()
N = int(input())
b = [input() for _ in range(N)]

for i in range(N):
  if b[i] in A:
    A[A.index(b[i])] = '.'
    
if (A[0] == '.' and A[3] == '.' and A[6] == '.') or (A[1] == '.' and A[4] == '.' and A[7] == '.')
or (A[2] == '.' and A[5] == '.' and A[8] == '.') or (A[0] == '.' and A[1] == '.' and A[2] == '.')
or (A[3] == '.' and A[4] == '.' and A[5] == '.') or (A[6] == '.' and A[7] == '.' and A[8] == '.')
or (A[0] == '.' and A[4] == '.' and A[8] == '.') or (A[2] == '.' and A[4] == '.' and A[6] == '.'):
  print('Yes')
else: print('No')

### FIXED CODE ###

A = []
A += input().split()
A += input().split()
A += input().split()
N = int(input())
b = [input() for _ in range(N)]
 
for i in range(N):
  if b[i] in A:
    A[A.index(b[i])] = '.'
    
if (A[0] == '.' and A[3] == '.' and A[6] == '.') or (A[1] == '.' and A[4] == '.' and A[7] == '.') or (A[2] == '.' and A[5] == '.' and A[8] == '.') or (A[0] == '.' and A[1] == '.' and A[2] == '.') or (A[3] == '.' and A[4] == '.' and A[5] == '.') or (A[6] == '.' and A[7] == '.' and A[8] == '.') or (A[0] == '.' and A[4] == '.' and A[8] == '.') or (A[2] == '.' and A[4] == '.' and A[6] == '.'): print('Yes')
else: print('No')
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


h, w = LI()
L = LIR(h)
for y in range(h):
    flag = False
    for x in range(w-1):
        if L[y][x] % 2:
            flag ^= True
        if flag:
            print(y+1, x+1, y+1, x+2)
    L[y][w-1] += flag



for y in range(h-1):
    flag = False
    if L[y][x] % 2:
        flag ^= True
    if flag:
        print(y + 1, h-1, y + 2, h-1)

### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


h, w = LI()
L = LIR(h)
ans = []
for y in range(h):
    flag = False
    for x in range(w-1):
        if L[y][x] % 2:
            flag ^= True
        if flag:
            ans += [[y+1, x+1, y+1, x+2]]
    L[y][w-1] += flag


flag = False
for y in range(h-1):
    if L[y][w-1] % 2:
        flag ^= True
    if flag:
        ans += [[y+1, w, y+2, w]]



print(len(ans))
for i in ans:
    print(*i)
N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    ai, bi, ci = map(int, input().split())
    edges[ai].append((bi, ci))
    edges[bi].append((ai, ci))
Q, K = map(int, input().split())

weighted_nodes = [0]*(N+1)
def add_weight(k, pre):
    for v in edges[k]:
        d, w = v
        if d != pre:
            weighted_nodes[d] = w + weighted_nodes[k]
            add_weight(d, k)
add_weight(K, -1)

for _ in range(Q):
    s, e = map(int, input().split()))
    print(weighted_nodes[s] + weighted_nodes[e])

### FIXED CODE ###

from collections import deque

N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    ai, bi, ci = map(int, input().split())
    edges[ai].append((bi, ci))
    edges[bi].append((ai, ci))
Q, K = map(int, input().split())

distance = [-1]*(N+1)
# def add_weight(k, pre):
#     for v in edges[k]:
#         d, w = v
#         if d != pre:
#             distance[d] = w + distance[k]
#             add_weight(d, k)
# add_weight(K, -1)
que = deque()
que.append(K); distance[K] = 0
while len(que):
    a = que.popleft()
    for b, c in edges[a]:
        if distance[b] == -1:
            distance[b] = c + distance[a]
            que.append(b)

# print(distance)

for _ in range(Q):
    s, e = map(int, input().split())
    print(distance[s] + distance[e])
K, N = map(int, input().split())
A = list(map(int, input().split())
distances = {}
for i in range(1, len(A) + 1):
	distances += (A[i] - A[i - 1]
most = max(distances.keys())
output = K - most
                  print(output)

### FIXED CODE ###

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

distance = []
for i in range(1, N):
	distance.append(A[i] - A[i - 1])
distance.append((A[0] + K - (A[-1])))
most = max(distance)
output = K - most
print(output)
a,b = map(int,input().split())
if a >b:
  print("GREATER")
elif a <b:
  print("LESS")
elif a==b:
  print("EQUAL")

### FIXED CODE ###

a = int(input())
b = int(input())
if a>b:
  print("GREATER")
elif a<b:
  print("LESS")
else:
  print("EQUAL")
import numpy as np

def dfs(v1):
    if all(visited): return 1
    visited[v1] = 1
    for v2 in range(n):
        if graph[v1][v2] == 0: continue
        if visited[v2] == 1: continue
        dfs(v2)
    return 0
# nは頂点の数
n, m = MI()
ab = np.array([list(map(int,input().split()))])
a,b = ab.T[0]-1,ab.T[1]-1

#隣接行列
graph = [[0] * n for _ in range(n)]

ans = 0
for a, b in zip(a,b):
    for aa,bb in zip(a,b): graph[aa][bb],graph[bb][aa] = 1,1
    graph[a][b],graph[b][a] = 0,0
    visited = [0]*n
    if not dfs(0): ans += 1

print(ans)



### FIXED CODE ###

import numpy as np

class unionfind: #ノード数nを読み込む
    def __init__(self,n): #コンストラクタ
        self.parent = list(range(n))
    def find(self,a): #根を探す、そのつど根を更新
        if self.parent[a] == a: return a #自分が根だったら終了
        p = self.find(self.parent[a])
        self.parent[a] = p #根をダイレクトに更新
        return p
    def unite(self,a,b): #ランク度外視で根を合体する
        pa,pb = self.find(a),self.find(b)
        if pa == pb: return 0 #根が一緒なら何もせず終了
        self.parent[pa] = pb
    def same(self,a,b):
        pa,pb = self.find(a),self.find(b)
        return pa == pb

n,m = map(int,input().split())
ab = np.array([list(map(int,input().split())) for i in range(m)])
a,b = ab.T[0] -1, ab.T[1] -1

ans = 0
for i in range(m): #除外する辺を決める
    uf = unionfind(n)
    connect = 0
    for j in range(m): #i以外の辺についてuniteしていく
        if i != j and not uf.same(a[j],b[j]): uf.unite(a[j],b[j]) ; connect += 1
    ans += 0 if connect == n-1 else 1
print(ans)
n=int(input())
S=input()
s=list(S)


def jokyolist(s):
  jokyo=[]
  #jokyo配列はこれから除去すべき奴の番号のリスト
  for i in range(len(s)-1):
    if s[i]==s[i+1]:
      jokyo.append(i)
    jokyo=sorted(jokyo,reverse=TRUE)
  return jokyo

def remov(s,jokyo):
  for i in range(len(jokyo)):
    s.pop(jokyo[i])
    return s
def removtimes(jokyo):
  t=len(jokyo)
  return t


while:
  jokyo=jokyolist(s)
  if removtimes(jokyo)==0:
    break:
  s=remov(s,jokyo)

print(len(s))


### FIXED CODE ###

n=int(input())
S=input()
s=list(S)

p=[]
#print(s)
for i in range(n-1):
  if s[i]==s[i+1]:
    p.append(i)
p.sort(reverse=True)
l=len(p)

for i in range(l):
    #print(p[i])
    s.pop(p[i])

print(len(s))
input()
A = list(map(int, input()))
count = 0

while all(a % 2 for a in A):
  A = [a/2 for a in A]
  count +=1
  
print(count)

### FIXED CODE ###

input()
A = list(map(int, input().split()))
count = 0

while all(a % 2 == 0 for a in A):
  A = [a/2 for a in A]
  count +=1
  
print(count)
n,x,t = map(int,input().split())

i = 0
while x*i>=n:
	i +=1

println(i*x)

### FIXED CODE ###

n,x,t = map(int,input().split())
i = 0
while x*i<n:
	i +=1
print(i*t)
import sys
def dfs(x, y, sym):
	tile[x][y] = "."
	for i in range(len(DX)):
		nx = x + DX[i]
		ny = y + DY[i]
		if 0<=nx and nx<N and 0<=ny and ny<M and tile[nx][ny] is sym:
			dfs(nx, ny, sym)

def solve():
	res = 0
	for i in range(N):
		for j in range(M):
			sym = tile[i][j]
			if tile[i][j] != ".":
				if tile[i][j] is sym:
					dfs(i, j, sym)
					res += 1
	print(res)

counter=0
DX = [-1, 0, 1, 0]
DY = [0, -1, 0, 1]
sys.setrecursionlimit(1000000)
tile = [[0 for i in range(1)] for j in range(1)]
while True:
	counter+=1
	line = input()
	if ' ' in line:
		nums = line.split(" ")
		N = int(nums[0])
		M = int(nums[1])
		tile = [[0 for i in range(N)] for j in range(M)]
	if N is 0 and M is 0:
		break
	else:
		tile[counter-2] = list(line)
	if (counter-1)==M:
		solve()
		counter = 0

### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys
def dfs(x, y, sym):
	tile[x][y] = "."
	for i in range(len(DX)):
		nx = x + DX[i]
		ny = y + DY[i]
		if (0<=nx and nx<N and 0<=ny and ny<M and tile[nx][ny] is sym):
			dfs(nx, ny, sym)

def solve():
	res = 0
	for i in range(N):
		for j in range(M):
			sym = tile[i][j]
			if tile[i][j] != ".":
				if tile[i][j] is sym:
					dfs(i, j, sym)
					res += 1
	print(res)

counter=0
DX = [-1,0,1,0]
DY = [0,-1,0,1]
sys.setrecursionlimit(10**7)
while True:
	line = input()
	if " " in line:
		nums = line.split(" ")
		N = int(nums[0])
		M = int(nums[1])
		tile = [[0 for i in range(M)] for j in range(N)]
	else:
		tile[counter-1] = list(line)
	if N is 0 and M is 0:
		break
	counter += 1
	if counter-1 is N:
		solve()
		counter = 0
x = input()
print x =^ 3

### FIXED CODE ###

x = input()
print x*x*x
import fractions

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

print((a*b)//fractions.gcd(a,b)

### FIXED CODE ###

import fractions
 
a,b = map(int, input().split())
 
print((a*b)//fractions.gcd(a,b))
a,b=map(int,input.split())

print(max(a+b,a-b,a＊b))


### FIXED CODE ###

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

print(max(a+b,a-b,a*b))
S=input()
num = len(S) - 1

for i in range(2**num):
    l = ['-']*num
    for j in range(num):
        if(i>>j)&1:
            l[num-j-1] = ['+']

    formula=""
    for l_num,l_m in zip(S,l+[""]):
        formula = l_num+l_m

    if eval(formula)==7:
        print(formula+'=7')
        break

### FIXED CODE ###

def dfs(i, Str, res):
    if i==3:
        if res==7:
            print(Str+"=7")
            exit()
        return
    
    dfs(i+1,Str+"+"+s[i+1],res+int(s[i+1]))
    dfs(i+1,Str+"-"+s[i+1],res-int(s[i+1]))

s=input()
dfs(0,s[0],int(s[0]))
N = int(input())
s = input()
r = 0
b = 0
for cap in s:
    if cap == 'R':
        r+=1
    elif cap == 'B':
        b+=1
if r>b:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

a,b,c = (int(x) for x in input().split())
if a == b and b == c:
    print('Yes')
else:
    print('No')
N = int(input())
A = list(map(int,input().split()))
import collections as col
 
num _list= set(A)
ca = col.Counter(A)

num = 0

for i in num_list:
    if ca[i] == 1:
        continue
    else:
        num += (ca[i]*(ca[i]-1))//2
        
for i in A:
    ans = num - (ca[i]-1)
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
import collections as col
 
num_list = set(A)
ca = col.Counter(A)

num = 0

for i in num_list:
    if ca[i] == 1:
        continue
    else:
        num += (ca[i]*(ca[i]-1))//2
        
for i in A:
    ans = num - (ca[i]-1)
    print(ans)
l1 = input().split()
a, b = list(map(int, l1))

l2 = input().split()
l2 = list(map(int, l2))

l3 = sorted(l2)
sum = l3[-1] + l3[-2] + l3[-3]
print(sum)


### FIXED CODE ###

l1 = input().split()
N, K = map(int, l1)
max  = K+1
l2 = input().split()
l2 = list(map(int, l2))

l3 = sorted(l2)
sum = 0


for i in range(1, max) :
    sum += l3[-i]

print(sum)
while True:
    (n, x) = [int(i) for i in input().split()]
    n = 3 < 100
    if n == x == 0:
        break
    print([1 if sum(n, x) == x else 0 for i in input.combinations(range(1, n + 1), 3)])

### FIXED CODE ###

while True:
    n, x = [int(i) for i in input().split()]

    if n == x == 0:
        break

    count = 0
    for s in range(1, n - 1):
        for m in range(s + 1, n):
            for e in range(m + 1, n + 1):
                if x == sum([s, m, e]):
                    count += 1

    print(count)
H,W = map(int,input().rstrip().split())
h,w = map(int,input().rstrip().split())
cells = [[1]*W]*H
del cells[:h]
cells = list(zip(*cells))
del cells[:w]
cells = list(zip(*cells))
print(sum(list(map(sum,[*cells]))))

### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W = map(int,input().rstrip().split())
h,w = map(int,input().rstrip().split())
cells = [[1]*W]*H
cells = cells[h:]
cells = list(zip(*cells))
cells = cells[w:]
print(sum(list(map(sum,list(zip(*cells))))))
H, W, M = map(int, input().split())
boms = set()
Hs = [0] * H
Ws = [0] * W
for i in range(M):
  h, w = map(lambda x: int(x) - 1, input().split())
  boms.add((h, w))
  Hs[h] += 1
  Ws[w] += 1
  
Hmax = max(Hs)
HMaxIndexs = set()
for i, h in enumerate(Hs):
  if h == Hmax:
    HMaxIndexs.add(i)

Wmax = max(Ws)
WMaxIndexs = set()
for i, w in enumerate(Ws):
  if w == Wmax:
    WMaxIndexs.add(i)

count = 0
for bom in boms:
  if (bom[0] in HMaxIndexs) and (bom[1] in WMaxIndexs):
    count += 1
print(Hmax + Wmax - 1) if count == len(HMaxIndexs) * len(WMaxIndexs) else print(Hmax + Wmax)



### FIXED CODE ###

from collections import deque

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
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def calc(n, k):
    if n == 0:
        return 0
    else:
        ans = 0
        digits = int(math.log10(n))+1
        #Nより小さい桁数
        if k <= digits-1:
            for n_dig in range(k, digits):
                ans += 9 * combinations_count(n_dig-1,k-1) * (9**(k-1))
                #print(n_dig,tot)
        #Nと桁数が同じ
        top = n//10**(digits-1)
        ans += (top-1) * combinations_count(digits-1,k-1) * (9**(k-1))
        if k>1:
            ans += calc(n-top*10**(digits-1), k-1)
        return ans
    

N = int(input())
K = int(input())

tot = calc(N,K)+1

print(tot)
    


### FIXED CODE ###

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def calc(n, k):
    if n < 10**(k-1):
        ans = 0
    elif n == 0:
        ans=0
    else:
        ans = 0
        digits = int(math.log10(n))+1
        #Nより小さい桁数
        if k <= digits-1:
            for n_dig in range(k, digits):
                ans += 9 * combinations_count(n_dig-1,k-1) * (9**(k-1))
                #print(n_dig,tot)
        #Nと桁数が同じ
        top = n//10**(digits-1)
        ans += (top-1) * combinations_count(digits-1,k-1) * (9**(k-1))
        if k>1:
            ans += calc(n-top*10**(digits-1), k-1)
        elif k==1:
            ans += 1
    #print(n,k,ans)
    return ans
    

N = int(input())
K = int(input())

tot = calc(N,K)

print(tot)
x = int(input())
x11 = x/11
num = [1,2,3,4,5,6]
num2= [7,8,9,10]

if x in num:
  print(1)
elif x in num2:
  print(2)

elif int(x11) == x11:
  print(int(x11)*2)
elif x+5 >int(x11)*2 + 6 >= x
  print(1+int(x11)*2)
else:
  print(2+int(x11)*2)


### FIXED CODE ###

x = int(input())
x11 = x/11
num = [1,2,3,4,5,6]
num2= [7,8,9,10]

if x in num:
  print(1)
  exit()
elif x in num2:
  print(2)
  exit()

elif int(x11) == x11:
  print(int(x11)*2)
  exit()
elif x > int(x11)*11 + 6:
  print(int(x11)*2 +2)
  exit()
else:
  print(1+int(x11)*2)
  exit()
s = input()

print("vowel") if s == a or s == i or s == u or s == e or s == o else print("consonant")

### FIXED CODE ###

s = input()

print("vowel") if s == "a" or s == "i" or s == "u" or s == "e" or s == "o" else print("consonant")
n,k=map(int,input().split())
h=list(map(int,input().split()))
if n<=k:
  print('0')
else:
  h.sort()
  h.pop([n-k:])
  print(sum(h))

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
if n<=k:
  print('0')
else:
  h.sort()
  for i in range(k):
    h.pop()
  print(sum(h))
n, a, b, k = map(int, input().split())

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
    
def mod_inv(a, mod):
    return (pow(a,mod-2,mod))

def mod_combination(n, k, mod):
    return (fact[n]*mod_inv(fact[k], mod)*mod_inv(fact[n-k], mod)) % mod

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

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

    
print(ans)


### FIXED 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(n+1):
    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)
params = input().rstrip().split('')
square = int(params[0]) * int(params[1])
length = (int(params[0]) + int(params[1])) * 2
 
print(square, length)

### FIXED CODE ###

(tate, yoko) = [int(x) for x in input().rstrip().split(' ')]
square = tate * yoko
length = (int(tate) + int(yoko)) * 2

print(square, length)
N=int(input())
a=list(map(int,input().split()))
ans=[]
b=0
for i in range(min(a),max(a)):
    for k in range(N):
        b+=(a[k]-i)**2
    ans.append(b)
    b=0
print(min(ans))

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
ans=[]
b=0
if N==1:
    print(0)
else:
    for i in range(min(a),max(a)+1):
        for k in range(N):
            b+=(a[k]-i)**2
        ans.append(b)
        b=0
    print(min(ans))
import sys

args = [int(input()) for i in range(6)]

 if (args[0] - arg[4]) > args[5]:
        print(":(")
        sys.exit()
print("Yay!")

### FIXED CODE ###

import sys

loops1 = 4
loops2 = 5
arg1 = 0
arg2 = 1

i=0
j=0

args = [int(input()) for i in range(6)]

for i in range(arg1,loops1):
	for j in range(arg2,loops2):
		if (args[j] - args[i]) > args[5]:
			print(":(")
			sys.exit()
print("Yay!")
import math
from functools import reduce

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

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

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

print(gcd_list(list_aaa))



### FIXED CODE ###

from fractions import gcd
from functools import reduce

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

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

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

mod = 10**9+7 #出力の制限
N = 2*(10**6)
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
a,b,c,d=map(int,input().split())
print(cmb(c+d+2,c+1,mod)-cmb(d+1+a,a,mod)-cmb(b+c+1,c+1,mod)+cmb(a+b,a,mod))

### FIXED CODE ###

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

mod = 10**9+7 #出力の制限
N = (2*(10**6))+5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
a,b,c,d=map(int,input().split())
print((cmb(c+d+2,c+1,mod)-cmb(d+1+a,a,mod)-cmb(b+c+1,c+1,mod)+cmb(a+b,a,mod))%mod)