Harryxun/stf_run huggingface dataset:
import sys
N, M = map(int, input().split())

if N == 1:
    sc = []
    for m in range(M):
        s, c = map(int, input().split())
        sc.append(c)
    print(min(sc))
    sys.exit(0)

if N == 2:
    sc = []
    for m in range(M):
        s, c = map(int, input().split())
        sc.append([s, c])
    
    l1 = []
    for m in range(M):
        if sc[m][0] == 1 and sc[m][1] > 0:
            l1.append(sc[m][1])
    if len(l1) == 0:
        print(-1)
        sys.exit(0)
    else:
        lank1 = min(l1)
    
    l2 = []
    for m in range(M):
        if sc[m][0] == 2:
            l2.append(sc[m][1])
    if len(l2) == 0:
        lank2 = 0
    else:
        lank2 = min(l2)
    
    ans = lank1 * 10 + lank2
    print(ans)
    sys.exit(0)
    
if N == 3:
    sc = []
    for m in range(M):
        s, c = map(int, input().split())
        sc.append([s, c])
        
    l1 = []
    for m in range(M):
        if sc[m][0] == 1 and sc[m][1] > 0:
            l1.append(sc[m][1])
    if len(l1) == 0:
        print(-1)
        sys.exit(0)
    else:
        lank1 = min(l1)
    
    l2 = []
    for m in range(M):
        if sc[m][0] == 2:
            l2.append(sc[m][1])
    if len(l2) == 0:
        lank2 = 0
    else:
        lank2 = min(l2)
    
    l3 = []
    for m in range(M):
        if sc[m][0] == 3:
            l3.append(sc[m][1])
    if len(l3) == 0:
        lank3 = 0
    else:
        lank3 = min(l3)
    
    ans = lank1 * 100 + lank2 * 10 + lank3
    print(ans)
    sys.exit(0)

### FIXED CODE ###

import sys
N, M = map(int,input().split())
s = []
c = []
for m in range(M):
    S, C = map(int,input().split())
    s.append(S)
    c.append(C)


for i in range(10 ** N):
    Str = str(i)

    if len(Str) == N and all([Str[s[m] - 1] == str(c[m]) for m in range(M)]):
        print(Str)
        sys.exit(0)

print(-1)
from scipy import special
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

mod = 1000000007

d = {}
for a, b in links:
    if a in d:
        d[a].add(b)
    else:
        d[a] = {b}
    if b in d:
        d[b].add(a)
    else:
        d[b] = {a}

if N == 1:
    print(K)
else:
    root = {1}
    ans = K
    while True:
        a = K - 2
        if 1 in root:
            a = K - 1
        children = set()
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            ans *= special.perm(a, b, exact=True)
            children |= d[i]
        else:
            if len(children) == 0:
                print(ans % mod)
                break
            root = children
            continue
        break

### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)
import sys
def input():
    return sys.stdin.readline()[:-1]
H,N=map(int,input().split())
l=[1000000000]*(H+1)
l[0]=0
for i in range(N):
    A,B=map(int,input().split())
    for j in range(1,A+1):
        if l[j]>B:
            l[j]=B
    for j in range(H):
        if j+A<=H:
            if l[j]+B<l[j+A]:
                l[j+A]=l[j]+B
print(l[-1])

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
H,N=map(int,input().split())
l=[1000000000]*(H+1)
l[0]=0
for i in range(N):
    A,B=map(int,input().split())
    for j in range(1,min(A+1,H+1)):
        if l[j]>B:
            l[j]=B
    for j in range(H):
        if j+A<=H:
            if l[j]+B<l[j+A]:
                l[j+A]=l[j]+B
print(l[-1])
n = int(input())
L = [int(i) for i in input().split()]
cnt = 0
ans = 1
for i in sorted(set(L),reverse=True):
  if L.count(i)>=4 and cnt==0:
    ans = i*i
    break
  elif 2<=L.count(i)<4:
    ans *= i
    cnt += 1
    if cnt == 2:
      break
  elif L.count(i)>=4 and cnt==1:
    ans *=i
    break
print(0 if ans==1 else ans)


### FIXED CODE ###

a, b, c= map(int, input().split())
if abs(a-b) > abs(a-c):
  print("B")
else:
  print("A")
n,m = map(int,input().split())
a = [list(map(int,input().split()))]
for i in range(10**n):
    tmp = str(i)
    if len(tmp)== n:
        f = True
        for s,c in a:
            if tmp[s-1] != str(c):
                f = False
                break
        if f:
            print(i)
            exit()
print(-1)

### FIXED CODE ###

n,m = map(int,input().split())
a = [list(map(int,input().split()))for i in range(m)]

for i in range(10**n):
    tmp = str(i)
    if len(tmp) == n:
        f = True
        for s,c in a:
            if tmp[s-1] != str(c):
                f = False
                break
        if f :
            print(i)
            exit()
print(-1)
a = []
while True:
    l = input().split
    if l == [0,0]:
        break
    a.append(l)
	

for i in range(len(a)):
	H,W = a[i]
	print("#" * W)
	print(("#"+"#"*(W-2)+"#"+"\n")*(H-2),end="")    # Python3
	print("#" * W)
	print("")

### FIXED CODE ###

a = []
while True:
    l = list(map(int,input().split()))
    if l == [0,0]:
        break
    a.append(l)


for i in range(len(a)):
	H,W = a[i]
	for i in range(H):
		print("#"*W)
	print("")
N, K = map(int, input().strip().split())
V = list(map(int, input().strip().split()))
H = []

maxi = 0
for i in range(N):
    for o in range(i):
        fs = 0
        bs = 0
        hand = []
        for p in range(o):
            fs += V[p]
            hand.append(V[p])
        for p in range(i-o, N):
            bs += V[p]
            hand.append(V[p])
        ts = fs + bs
        if ts > maxi:
            maxi = ts
        if len(hand) > 0:
            hand.sort()
            for j in range(K-i):
                if hand[0] <= 0:
                    del hand[0]
                else:
                    break
        ts = 0
        for k in hand:
            ts += k
        if ts > maxi:
            maxi = ts
print(maxi)

### FIXED CODE ###

N, K = map(int, input().strip().split())
V = list(map(int, input().strip().split()))
H = []
maxi = 0
for i in range(min(N, K)):
    for o in range(i+2):  # error1
        ts = 0
        hand = []
        for p in range(o):
            hand.append(V[p])
        for p in range(N-(i-o)-1, N):  # error2
            hand.append(V[p])
        for values in hand:
            ts += values
        if ts > maxi:
            maxi = ts
        if len(hand) > 0:
            hand.sort()
            for j in range(K-i-1):  # error3
                if len(hand) > 0:
                    if hand[0] < 0:
                        del hand[0]
                    else:
                        break
        ts = 0
        for k in hand:
            ts += k
        if ts > maxi:
            maxi = ts
print(maxi)
field = []
w = 0
h = 0


def main():
    global field, w, h
    while True:
        h, w = map(int, input().split())
        if h == 0 and w == 0:
            break
        count = 0
        [field.append([_ for _ in input()]) for _ in range(h)]
        print(field)
        for y in range(h):
            for x in range(w):
                if field[y][x] != -1:
                    dfs(field[y][x], x, y)
                    count += 1
        print(count)


def arrangement(kinds, y):
    global field
    for i, kind in enumerate(kinds):
        field[y][i] = kind


def dfs(kind, x, y):
    global field
    print(x, y, field[y][x])
    field[y][x] = -1
    for dx, dy in zip([0, 0, -1, 1], [1, -1, 0, 0]):
        next_x = x + dx
        next_y = y + dy
        if next_x < 0 or next_y < 0 or next_x >= w or next_y >= h:
            continue
        if field[next_y][next_x] != kind:
            continue

        dfs(field[next_y][next_x], next_x, next_y)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(20000)

field = []
w = 0
h = 0


def main():
    global field, w, h
    while True:
        h, w = map(int, input().split())
        if h == 0 and w == 0:
            break
        count = 0
        field = []
        [field.append(list(input())) for _ in range(h)]
        for y in range(h):
            for x in range(w):
                if field[y][x] != -1:
                    dfs(field[y][x], x, y)
                    count += 1
        print(count)


def dfs(kind, x, y):
    global field
    field[y][x] = -1
    for dx, dy in zip([0, 0, -1, 1], [1, -1, 0, 0]):
        next_x = x + dx
        next_y = y + dy
        if next_x < 0 or next_y < 0 or next_x >= w or next_y >= h \
                or field[next_y][next_x] != kind:
            continue
        dfs(field[next_y][next_x], next_x, next_y)


if __name__ == '__main__':
    main()
s=input()
if s[0:1]!='A':
  print('WA')
  exit()
t=s[2:len(s)-1]
countc=0
for i in range(len(t)):
  if t[i]=='C':
    countc+=1
if countc!=1:
  print('WA')
  exit()
for i in range(1,len(s)):
  if s[i:i+1]!='C' and s[i:i+1].isupper():
    print('WA')
    exit()
print('AC')

















for i in range(100*d):
  for j in range(d):
    if i+1==p[j]:
      tugi=max(tugi,j+1+c[j])
    elif i+1<p[j]:
      tugi=max(tugi,j+1)
  ten+=tugi
  tugi=0
  print(ten)
  if ten>=g:
    print(i+1)
    exit()

### FIXED CODE ###

S = input()
abc = 'abcdefghijklmnopqrstuvwxyz'
if S[0] == 'A':
  if S[2:len(S)-1].count('C') == 1:
    for c in S:
      if (c!='A') and (c!='C') and (c not in abc):
        print('WA')
        exit()
    else:
      print('AC')
  else:
    print('WA')
else:
  print('WA')
import numpy as np
import math
n = int(input())
A = np.fromstring(input(),dtype=np.int64,sep=" ")
rng = int(math.log2(np.max(A)))+1
sum = 0
for bit in range(rng):
    c = int((A & 1).sum())
    sum += c *(n-c)*(1<<bit)
    A = A>>1

print(sum %(10**9+7))

### FIXED CODE ###

import numpy as np
 
 
def solve(string):
    n, *a = map(int, string.split())
    # a = ["{:060b}".format(_a) for _a in a]
    a = np.asarray(a, dtype=np.int64)
    m = 10**9 + 7
    ans = 0
    for i in range(60):
        s = int((a & 1).sum())
        a >>= 1
        # ans += s * (n - s) * pow(2, 59 - i, m)
        ans += s * (n - s) * pow(2, i, m) % m
        ans %= m
    return str(ans)
 
 
if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))
x = int(input())
if x == 3 or x == 5 or X == 7:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

x = int(input())
if x == 3 or x == 5 or x == 7:
    print('YES')
else:
    print('NO')
a = input()
print a.swapcase()

### FIXED CODE ###

a = raw_input()
print a.swapcase()
N, K = map(int, input().split())

# x_1 + x_2 + ... x_k = n
# x_i >= 0
# k個の箱にn個のボールを入れる重複組み合わせ　n+k-1_C_k-1
# n個の玉とk-1個の仕切りを並べる

# x_1 + x_2 + ... x_k = n
# x_i >= 1
# k個の箱にn個のボールを1個以上入れる重複組み合わせ　n-1_C_k-1
# n個の玉の仕切りn-1個の中に、k-1箇所仕切りを入れる

from math import factorial

# k = 1,2,...,K
for k in range(1, K + 1):

    # k = 1,2,...,K
    # K個の青いボールをk個に分割する方法
    # K-1_C_k-1
    c1 = factorial(K - 1) / factorial(K - k) / factorial(k - 1)
    c1 = int(c1) % (10 ** 9 + 7)

    # N-K個の赤いボールの分割
    # k+1個に分割(しかし両端はなくても良い)
    # N-K+1_C_k

    # x_1 + x_2 + ... + x_k + x_k+1 = N−K
    # x1 >= 0
    # x_2,x_3,...,x_k >= 1
    # x_k + 1 >= 0

    c2 = factorial(N - K + 1) / factorial(N - K - k + 1) / factorial(k)
    c2 = int(c2) % (10**9 + 7)

    ans = c1 * c2 % (10**9 + 7)
    print(ans)


### FIXED CODE ###

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

# x_1 + x_2 + ... x_k = n
# x_i >= 0
# k個の箱にn個のボールを入れる重複組み合わせ　n+k-1_C_k-1
# n個の玉とk-1個の仕切りを並べる

# x_1 + x_2 + ... x_k = n
# x_i >= 1
# k個の箱にn個のボールを1個以上入れる重複組み合わせ　n-1_C_k-1
# n個の玉の仕切りn-1個の中に、k-1箇所仕切りを入れる

from math import factorial

# k = 1,2,...,K
for k in range(1, K + 1):
    if k > N - K + 1:
        print(0)
        continue

    # k = 1,2,...,K
    # K個の青いボールをk個に分割する方法
    # K-1_C_k-1
    c1 = factorial(K - 1) // (factorial(K - k) * factorial(k - 1))
    c1 = int(c1) % (10 ** 9 + 7)

    # N-K個の赤いボールの分割
    # k+1個に分割(しかし両端はなくても良い)
    # N-K+1_C_k

    # x_1 + x_2 + ... + x_k + x_k+1 = N−K
    # x1 >= 0
    # x_2,x_3,...,x_k >= 1
    # x_k + 1 >= 0

    c2 = factorial(N - K + 1) // (factorial(N - K - k + 1) * factorial(k))
    c2 = int(c2) % (10**9 + 7)

    ans = c1 * c2 % (10**9 + 7)
    print(ans)
I = input()
K = ['Sunny', 'Cloudy,''Rainy', 'Sunny']
Idx = K.index(I)
print(K[Idx+1])


### FIXED CODE ###

I = input()
K = ['Sunny', 'Cloudy', 'Rainy', 'Sunny']
Idx = K.index(I)
print(K[Idx+1])
N = int(input())
A = list(map(int, input().split()))
ans = N
for i in range(N-1):
    wa = 0
    if A[i] & A[i+1] != 0:
        continue
    ans += 1
    wa = A[i] ^ A[i+1]
    for j in range(i+2, 20):  # 全部0だった時にTLEを起こす
        if wa & A[j] == 0:
            wa = wa ^ A[j]
            ans += 1
        else:
            break
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
l,r = 0,0
ans = 0
s = 0
while l < n:
  if r < n and s+a[r] == s^a[r]:
    s += a[r]
    r += 1
    #print(s)
  else:
    ans += r-l
    s -= a[l]
    #print(s)
    l += 1

print(ans)
N=int(input())
print(N.count("1"))

### FIXED CODE ###

N=input()
print(N.count("1"))
N=int(input())
A=list(map(int, input().split()))
S=A[0]
for i in range(N-1):
  S=S^A[i+1]
L=[0]*N
for i in range(N):
  L[i]=A[i]^S
print(*L)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
S=A[0]
for i in range(N-1):
  S=S^A[i+1]
L=[0]*N
for i in range(N):
  L[i]=A[i]^S
print(*L)
n = int(input())
edges = [[] for _ in range(n * 1001)]
memo = []
for i in range(n):
    A = list(map(int, input().split()))
    for j in range(n-1):
        if i < A[j] - 1:
            A[j] = i * 1000 + A[j] - 1
        else:
            A[j] = (A[j] - 1) * 1000 + i

    for j in range(n-2):
        edges[A[j]].append(A[j+1])
    memo.append(A[0])

seen = [False for _ in range(1001 * n)]
def dfs(start, frm, cur, flg):
    for to in edges[cur]:
        if to == frm:
            continue
        if to == start:
            return False
        else:
            d[to] = max(d[cur] + 1, d[to])
            flg = dfs(start, cur, to, flg)

    return flg


flg = True
ans = []
for x in memo:
    d = [0 for _ in range(n * 1001)]
    d[x] = 1
    if dfs(x, -1, x, True):
        ans.append(max(d))
    else:
        flg = False

if flg:
    print(max(ans))
else:
    print(-1)

### FIXED CODE ###

from collections import Counter
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
n = int(input())
edges = [[] for _ in range(n * 1001)]
memo = []
start = set()
for i in range(n):
    A = list(map(int, input().split()))
    for j in range(n-1):
        if i < A[j] - 1:
            A[j] = i * 1000 + A[j] - 1
        else:
            A[j] = (A[j] - 1) * 1000 + i

    for j in range(n-2):
        edges[A[j]].append(A[j+1])
    memo.append(A[0])

memo = Counter(memo).most_common()
for x, t in memo:
    if t > 1:
        start.add(x)

#閉路検出/最長のパス
d = [-1 for _ in range(1001 * n)]
def dfs(v):
    d[v] = -2
    l = 0
    for to in edges[v]:
        if d[to] == -2:
            print(-1)
            exit()
        if d[to] == -1:
            dfs(to)
        l = max(l, d[to] + 1)
    d[v] = l

if len(start) == 0:
    print(-1)
    exit()
for i in start:
    dfs(i)
print(max(d) + 1)
n, k = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * n
    a[0] = 0
    for i in range(1, n):
        hi = h[i]
        a[i] = min(a[j] + abs(hi - h[j]) for j in range(max(0, i - k), i))
    print(a[-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
a = [0] * n
a[0] = 0
for i in range(1, n):
      hi = h[i]
      a[i] = min(a[j] + abs(hi - h[j]) for j in range(max(0, i - k), i))
print(a[-1])
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    while p<n and a[q]+a[p]<=md:
            p+=1
    if p==n: break
    try:
        cnt+=n-p
        ans+=int(a[q])*(n-p)*2
    except:
        ans=ans


ans+=(m-cnt)*md
print(ans)

### FIXED CODE ###

import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2
md=(r+l)//2
while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)
S = input()
T = input()

l = len(T)

ans = []
for i in range(len(S)-l):
    cnt = 0
    for n in range(l):
        if S[i+n] != T[n]:
            cnt += 1
    ans.append(cnt)
    
print(min(ans))


### FIXED CODE ###

S = input()
T = input()

l = len(T)

if l == len(S):
    cnt = 0
    for i in range(l):
        if S[i] != T[i]:
            cnt += 1
    print(cnt)
    exit()

ans = []
for i in range(len(S)-l):
    cnt = 0
    for n in range(l):
        if S[i+n] != T[n]:
            cnt += 1
    ans.append(cnt)
    
print(min(ans))
import numpy as np

N, K, Q, *A, = map(int,map(lambda x: ''.join(sorted(x)), open(0).read().split()))
P = np.zeros(N)
for i in A:
    P[i - 1] += 1
for j in P:
    if K <= Q - j:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

import numpy as np

N, K, Q, *A, = map(int, open(0).read().split())
P = np.zeros(N)
for i in A:
    P[i - 1] += 1
for j in P:
    if K <= Q - j:
        print("No")
    else:
        print("Yes")
n=int(input())
p=[list(map(int,input().split())) for _ in [0]*(n-1)]
g=[[] for _ in [0]*n]

[g[a-1].append(b-1) for a,b in p]
[g[b-1].append(a-1) for a,b in p]

memo=[False for _ in [0]*n]
q=[0]
memo[0]=True
last=0
while(q):
	qq=[]
	for i in q:
		for j in g[i]:
			if memo[j]==False:
				memo[j]=True
				last=j
				qq.append(j)
	q=qq

memo=[False for _ in [0]*n]
q=[last]
memo[0]=True
cnt=0
while(q):
	cnt+=1
	qq=[]
	for i in q:
		for j in g[i]:
			if memo[j]==False:
				memo[j]=True
				qq.append(j)
	q=qq
	
if cnt%3==2:
	print('Second')
else:
	print('First')

### FIXED CODE ###

n,x,y=map(int,input().split())
a=list(map(int,input().split()))
if len(a)==1:a=a+a
print(max(abs(y-a[-1]),abs(a[-1]-a[-2])))
input = int(input())
n = input // 100
m = input % 100
if m // n <= 5:
    print(1)
else:
    print(0)

### FIXED CODE ###

input = int(input())
n = input // 100
if n > 0:
    m = input % 100
    if m / n <= 5:
        print(1)
    else:
        print(0)
else:
    print(0)
N,K=map(int,input().split())
H=list(map(int,input().split()))
H.sort(reverse=True)
for i in range(K):
  H.remove(H[i])
print(K+sum(H[K:]))

### FIXED CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
H.sort(reverse=True)
print(sum(H[K:]))
import fractions
N=int(input())
A=list(map(int,input().split()))
c=1
a=0
w=10**9+7
for A_ in A:
    c_=c*A_//fractions.gcd(c,A_)
    a=(a*c_/c+c_/A_)%w
    c=c_
print(int(a))

### FIXED CODE ###

import fractions
N=int(input())
A=list(map(int,input().split()))
c=1
a=0
w=10**9+7
for A_ in A:
    c=c*A_//fractions.gcd(c,A_)
for A_ in A:
    a+=c//A_
print(int(a%w))
import math
A, B, C, D = list(map(int, input().split()))
A_ = A - 1
B_res = B - (B//C + B//D - B//int(C*D/math.gcd(C, D)))
A_res = A_ - (A_//C + A_//D - A_//int(C*D/math.gcd(C, D)))
print(B_res - A_res)

### FIXED CODE ###

def gcd(a, b):
    if a < b:
        tmp = a
        a = b
        b = tmp

    r = a % b
    while r!=0:
        a = b
        b = r
        r = a % b
    return b

def lcm(a, b):
    return int(a * b / gcd(a, b))

A, B, C, D = list(map(int, input().split()))
A_ = A - 1
lcm_CD = lcm(C, D)
B_res = B - (B//C + B//D - B//lcm_CD)
A_res = A_ - (A_//C + A_//D - A_//lcm_CD)
print(B_res - A_res)
N, K = map(int, input().split())

def calc(x, y):
  if y == 1:
    print(0)
    return
  z = abs(x-y)
  if z > abs(z-y):
    calc(z, y)
  else:
    print(z)
  
calc(N, K)

### FIXED CODE ###

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

if N > K:
  N = N % K

ans = min(N, abs(N-K))
print(ans)
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

comb = Combination(10**5)

def main():
    H, W, A, B = map(int, input().split())
    ans = 0
    for i in range(1, H - A + 1):
        ans += comb(i + B - 2, i - 1) * comb(H - i + W - B - 1, H - i)
        ans %= mod
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

comb = Combination(10**6)

def main():
    H, W, A, B = map(int, input().split())
    ans = 0
    for i in range(1, H - A + 1):
        ans += comb(i + B - 2, i - 1) * comb(H - i + W - B - 1, H - i)
        ans %= mod
    print(ans)


if __name__ == "__main__":
    main()