Harryxun/stf_run huggingface dataset:
n, m = list(map(int, input().split()))

s = [0]*m
c = [0]*m

for k in range(m):
    s[k], c[k] = list(map(int, input().split()))

for l in range(m):
    if n == 1:
        if s[l] != 1:
            print(-1)
            exit()
    elif n == 2:
        if s[l] == 3 or (s[l] == 1 and c[l] == 0):
            print(-1)
            exit()
    elif n == 3:
        if s[l] == 1 and c[l] == 0:
            print(-1)
            exit()

if n == 1:
    kaishi = 0
    owari = 10
elif n == 2:
    kaishi = 10
    owari = 100
elif n == 3:
    kaishi = 100
    owari = 1000

for num in range (kaishi, owari):
    seigo = 1
    for i in range(m):
        if s[i] == 3:
            if num%10 == c[i]:
                continue
            else:
                seigo = 0
        if s[i] == 2:
            if (num//100) == 0 and (num%100)//10 == 0:
                seigo = 0 
            elif (num%100)//10 == c[i]:
                continue
            else:
                seigo = 0
        if s[i] == 1:
            elif (num%10) == c[i]:
                continue
            else:
                seigo = 0

    if seigo == 1:
        print(num)
        exit()
        
print(-1)





### FIXED CODE ###

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

s = [0]*(m+1)
c = [0]*(m+1)

for k in range(m):
    s[k], c[k] = list(map(int, input().split()))

for l in range(m):
    if n == 1:
        if s[l] != 1:
            print(-1)
            exit()
    elif n == 2:
        if s[l] == 3 or (s[l] == 1 and c[l] == 0):
            print(-1)
            exit()
    elif n == 3:
        if s[l] == 1 and c[l] == 0:
            print(-1)
            exit()

if n == 1:
    for num in range(0, 10):
        seigo = 1
        for i in range(m):
            if num != c[i]:
                seigo = 0
        if seigo == 1:
            print(num)
            exit()
    print(-1)
    exit()
elif n == 2:
    for num in range(10, 100):
        seigo = 1
        for i in range(m):
            if s[i] == 1:
                if num//10 != c[i]:
                    seigo = 0
            if s[i] == 2:
                if num%10 != c[i]:
                    seigo = 0
        if seigo == 1:
            print(num)
            exit()
    print(-1)
    exit()
else:
    for num in range(100, 1000):
        seigo = 1
        for i in range(m):
            if s[i] == 1:
                if num//100 != c[i]:
                    seigo = 0
            elif s[i] == 2:
                if (num-100*(num//100))//10 != c[i]:
                    seigo = 0
            elif s[i] == 3:
                if num%10 != c[i]:
                    seigo = 0
        if seigo == 1:
            print(num)
            exit()
    print(-1)
    exit()
V,E = map(int, input().split())
#??£??\??????????????????
A = [[] for i in range(V)]
for i in range(E):
    s,t = map(int, input().split())
    A[s].append(t)
    A[t].append(s)
    
#?????????????¨???????
prenum = [None for i in range(V)]
#DFS???????????????????????????
parent = [None for i in range(V)]
#????????????????°??????????
lowest = [None for i in range(V)]
#?¨????????????°??????
visited = [False for i in range(V)]

def DFS(u = 0, prev = -1, timer = 0):
    prenum[u] = timer
    lowest[u] = timer
    timer += 1
    visited[u] = True
    
    for v in A[u]:
        if not visited[v]:
            parent[v] = u
            DFS(v, u, timer)
            lowest[u] = min(lowest[u], lowest[v])
        elif v != prev:
            lowest[u] = min(lowest[u], prenum[v])
DFS()

ans = set()
 
for u in range(1, V):
    p = parent[u]
    if prenum[p] <= lowest[u]:
        ans.add(p)
 
if parent.count(0) >= 2:
    ans.add(0)
else:
    ans.discard(0)
 
ans = list(ans)
ans.sort()
 
if ans:
    print(*ans, sep = '\n')

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

V,E = map(int, input().split())
#???£??\??????????????????
A = [[] for i in range(V)]
for i in range(E):
    s,t = map(int, input().split())
    A[s].append(t)
    A[t].append(s)
     
#??????????????¨???????
prenum = [None for i in range(V)]
#DFS???????????????????????????
parent = [None for i in range(V)]
#?????????????????°??????????
lowest = [None for i in range(V)]
#??¨?????????????°??????
visited = [False for i in range(V)]
 
def DFS(u = 0, prev = -1, timer = 0):
    prenum[u] = timer
    lowest[u] = timer
    timer += 1
    visited[u] = True
     
    for v in A[u]:
        if not visited[v]:
            parent[v] = u
            DFS(v, u, timer)
            lowest[u] = min(lowest[u], lowest[v])
        elif v != prev:
            lowest[u] = min(lowest[u], prenum[v])
DFS()
 
ans = set()
  
for u in range(1, V):
    p = parent[u]
    if prenum[p] <= lowest[u]:
        ans.add(p)
  
if parent.count(0) >= 2:
    ans.add(0)
else:
    ans.discard(0)
  
ans = list(ans)
ans.sort()
  
if ans:
    print(*ans, sep = '\n')
def dfs(i, total, S, remain):
    global ans
    if i == D:
        if S < G:
           """
           If all the problems of the segment don't have to be calculated,
           it is preferable to solve some of the segment with the highest rate.
           """
           use = max(remain)
           N = min(L[use-1][0], (G-S)//(100*L[use-1][0])
           S += 100 * N * use
           total += N
           
        if S >= G:
        ans = min(ans, total)
    else:
        dfs(i+1, total, S, remain)
        dfs(i+1, total + L[i+1][0], S + 100 * (i+1) * L[i+1][0] + L[i+1][1], remain - (i+1))

D, G = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(D)]
ans = 10 ** 9

dfs(0, 0, 0, set(range(1, D+1)))

print(ans)

### FIXED CODE ###

# まだ解いてない配点を nokori として持つ
def dfs(i, sum, count, nokori):
    global ans
    if i == d:
        # G 点に満たなければ nokori のうち一番大きいものを解く
        if sum < g:
            use = max(nokori)
            # 解く問題が問題数を超えないように注意
            n = min(pc[use - 1][0], -(-(g - sum) // (use * 100)))
            count += n
            sum += n * use * 100

        if sum >= g:
            ans = min(ans, count)
    else:
        # 総合スコア、解いた問題数、まだ解いてない問題を更新
        dfs(i + 1, sum, count, nokori)
        dfs(i + 1, sum + pc[i][0] * (i + 1) * 100 + pc[i][1], count + pc[i][0], nokori - {i + 1})


d, g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]

ans = float("inf")

dfs(0, 0, 0, set(range(1, d + 1)))
print(ans)
list1 = list(map(int, input().split()))


for i in range(1,5):
  if list1[i-1] != i:
    return(i)


### FIXED CODE ###

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


for i in range(1,6):
  if list1[i-1] != i:
    print(i)
retu = "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51"

retuint = map(int,retu.split(","))

index=input()

print(retuint(index))

### FIXED CODE ###

retu = "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51"

retu = retu.split(",")
retuint=[]
for i in retu :
	retuint.append(int(i))

index=input()

print(retuint[int(index)-1])
n,a = map(int, input().split())
x = list(map(lambda x:int(x)-a, input().split()))
y = max(x)

dp = [[0]*(2*n*y+1) for _ in range(n+1)]
dp[0][n*y] = 1
for k in range(n):
    for i in range(2*n*y+1):
        if i+x[k] < 0 or i+x[k] > 2*n*y:
            dp[k+1][i] = dp[k][i]
        else:
            dp[k+1][i] = dp[k][i] + dp[k][i+x[k]]
print(dp[-1][n*y]-1)


### FIXED CODE ###

n,a = map(int, input().split())
x = list(map(int, input().split()))
y = max(x)
x = [z-a for z in x]

dp = [[0]*(2*n*y+1) for _ in range(n+1)]
dp[0][n*y] = 1
for k in range(n):
    for i in range(2*n*y+1):
        res = dp[k][i]
        if i+x[k] < 0 or i+x[k] > 2*n*y:
            pass
        else:
            res += dp[k][i+x[k]]
        dp[k+1][i] = res
print(dp[-1][n*y]-1)
a, b = [input(i) for i in input().split()]
print(a, b)

### FIXED CODE ###

a, b = [int(i) for i in input().split()]
print(a * b, (a + b) * 2)
a1=int(input())
a2=int(input())
a3=int(input())
if a1+a2+a3>=22 :
    print('bust')
elif a1+a2+a3<22 :
    print('win')

### FIXED CODE ###

a1,a2,a3=map(int,input().split())
if a1+a2+a3>=22 :
    print('bust')
elif a1+a2+a3<22 :
    print('win')
def fill0(s,x,y):
	if 0 <= x <= W-1 and 0 <= y <= H-1 and A[y][x] == s:
		A[y][x] = 0
		fill0(s,x+1,y); fill0(s,x,y+1); fill0(s,x-1,y); fill0(s,x,y-1)
	return
while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	A = [list(raw_input()) for i in range(H)]
	ans = 0
	for y in range(H):
		for x in range(W):
			if A[y][x] in ["#","@","*"]:
				fill0(A[y][x],x,y)
				ans += 1
	print ans

### FIXED CODE ###

import sys
sys.setrecursionlimit(20000)
def solve(h,w,count,c):
    if 0 <= h < H and 0 <= w < W and A[h][w] == c:
        A[h][w] = count
        for dh,dw in zip([1,0,-1,0],[0,1,0,-1]):
            solve(h+dh,w+dw,count,c)
while 1:
    H,W = map(int,raw_input().split())
    if H == W == 0: break
    A = [list(raw_input()) for _ in range(H)]
    count = 0
    for h in range(H):
        for w in range(W):
            if type(A[h][w]) is not int:
                solve(h,w,count,A[h][w])
                count += 1
    print count
# -*- coding: utf-8 -*-

import sys

def check(a, b, x):
    if int(x * 0.08) != a or int(x * 0.1) != b:
        return -1
    return x

def prob_c(a, b):
    yasu = a * 100 / 8
    yasutaka = (a+0.99) * 100 / 8
    taka = b * 100 / 10
    takataka = (b+0.99) * 100 / 10
    ans = check(a, b, max(yasu, taka))
    print(f'{ans}')

if __name__ == '__main__':
    a, b = map(int, input().split())
    prob_c(a,b)
    


### FIXED CODE ###

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

from math import ceil

def check(a, b, x):
    if int(x * 0.08) != a or int(x * 0.1) != b:
        return -1
    return x

def prob_c(a, b):
    yasu = ceil(a * 100 / 8)
    taka = ceil(b * 100 / 10)
    ans = int(check(a, b, max(yasu, taka)))
    print(ans)

if __name__ == '__main__':
    a, b = map(int, input().split())
    prob_c(a,b)
def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item or (list[mid - 1] < item and list[mid + 1] > item):
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1

    return None


N = int(input())
str_l = input()
num = 0
L = []
for v in str_l.split(' '):
    L.push(int(v))

L.sort()
for i in range(N):
    Ldash = L
    a = Ldash.pop(i)
    for j in range(N - 1):
        b = Ldash.pop(j)
        index = binary_search(Ldash, a + b)
        if index is None:
            continue
        else:
            for k in range(index + 1):
                c = Ldash[k]
                if b + c > a and a + c < b:
                    num += 1

print(num)

### FIXED CODE ###

import bisect


N = int(input())
str_l = input()
num = 0
L = []
for v in str_l.split(' '):
    L.append(int(v))

L.sort()
for i in range(N - 1):
    a = L[i]
    for j in range(i, N - 2):
        b = L[j + 1]
        index = bisect.bisect_left(L[j + 2:], a + b)
        num += index
        # for k in range(0, index):
        #     c = (L[j + 2:])[k]
        #     if b + c > a and a + c > b:
        #         num += 1

print(num)
i=1
while 1:
??a=input()
??if int(a)==0:break
 print(f'Case {i}: {a[i]}')
 i+=1

### FIXED CODE ###

import sys
i=1
for e in sys.stdin:
 if'0\n'==e:break
 print(f'Case {i}: {e[:-1]}');i+=1
N = int(input())

cnt = 0
tmp = 0

while tmp<=N:
    if N==1:
        print(ans)
        break
    else:
        cnt += 1
        tmp = 2**cnt

print(2**(cnt-1))

### FIXED CODE ###

N = int(input())

cnt = 0
tmp = 0

while tmp<=N:
    cnt += 1
    tmp = 2**cnt

print(2**(cnt-1))
N,K=map(int,input().split())
i=0
while N>K=**i:
    i+=1
print(i)

### FIXED CODE ###

N,K=map(int,input().split())
i=0
while N>=K**i:
    i+=1
print(i)
D, N = map(int, input().split())
if D == 0:
  if N == 100:
    print(101)
  else:
  	print(N)
elif D == 1:
  if N == 10000:
    print(10100)
  else:
  	print(N*100)
else:
  if N == 100
    print(1000100)
  else:
    print(N*10000)


### FIXED CODE ###

D, N = map(int, input().split())
if D == 0:
  if N == 100:
    print(101)
  else:
  	print(N)
elif D == 1:
  if N == 100:
    print(10100)
  else:
    print(N*100)
else:
  if N == 100:
    print(1010000)
  else:
    print(N*10000)
# 解説を参考に作成

# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
import math
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, K, As):
    ans = max(As)
    l, r = 1, ans
    for _ in range(30):
        m = (l + r) // 2
        cnt = 0
        for A in As:
            cnt += math.ceil(A / m) - 1
        if cnt <= K:
            ans = min(ans, m)
            r = m - 1
        else:
            l = m + 1
        if l == r:
            break
    print(ans)


if __name__ == '__main__':
    # S = input()
    # N = int(input())
    N, K = map(int, input().split())
    As = [int(i) for i in input().split()]
    # Bs = [int(i) for i in input().split()]
    solve(N, K, As)


### FIXED CODE ###

# 解説を参考に作成

# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
import math
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, K, As):
    ans = max(As)
    l, r = 1, ans
    for _ in range(30):
        m = (l + r) // 2
        if m <= 0:
            break
        cnt = 0
        for A in As:
            cnt += math.ceil(A / m) - 1
        if cnt <= K:
            ans = min(ans, m)
            r = m - 1
        else:
            l = m + 1
    print(ans)


if __name__ == '__main__':
    # S = input()
    # N = int(input())
    N, K = map(int, input().split())
    As = [int(i) for i in input().split()]
    # Bs = [int(i) for i in input().split()]
    solve(N, K, As)
# -*- coding: utf-8 -*-
h,w,d = map(int, input().split())
dd = {}
field = []
for hi in range(h):
    line = list(map(int, input().split()))
    field.append(line)
    for wi in range(w):
        dd[line[wi]] = (hi, wi)
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]

memo = [[-1 for _ in range(h*w)] for _ in range(h*w)]
def calc(s,r):
    if s==r:
        return 0
    elif memo[s][r]>0:
        return memo[s][r]

    h1,w1 = dd[s]
    s2 = field[h1][w1]+d
    h2,w2 = dd[s2]
    res = abs(h1-h2) + abs(w1-w2) + calc(s2, r)
    memo[s][r] = res
    return res

for (l,r) in lr:
    print(calc(l,r))


### FIXED CODE ###

# coding=utf-8
line = input().split(" ")
h = int(line[0])
w = int(line[1])
d = int(line[2])

table = [0 for _ in range(h*w+1)]
for hi in range(h):
    line = list(map(int, input().split(" ")))

    for wi in range(w):
        table[line[wi]] = (hi+1, wi+1)

def calc(l,r):
    ret = 0
    if l!=r:
        c1 = table[l]
        c2 = table[r]
        ret += abs(c1[0]-c2[0])+abs(c1[1]-c2[1])
    return ret

acc = [0 for _ in range(h*w+1)]
for dd in range(1,d+1):
    s = dd+d
    while s<=h*w:
        acc[s] = calc(s-d,s)+acc[s-d]
        s += d

q = int(input())
for _ in range(q):
    line = input().split(" ")
    l = int(line[0])
    r = int(line[1])

    ret = acc[r] - acc[l]
    print(ret)
lines = []
while True:
    line = input()
    if line:
        lines.append(line)
    else:
        break

c = 0
p = 0
curr_no = -1
for line in lines[1:]:
    curr = line.split()
    if(curr_no != curr[0]):
        curr_no = curr[0]
        curr_flag = True
    if(curr_flag):
        if(curr[1] == "AC"):
            c += 1
            curr_flag = False
        else:
            p += 1

print(str(c) + " " + str(p))


### FIXED CODE ###

from collections import defaultdict

params = input().split()
n = int(params[0])
m = int(params[1])

penaltyCount = dict()
penaltyCount = defaultdict(lambda: 0, penaltyCount)

correct = 0
penalty = 0

for i in range(m):
    submission = input().split()
    p = int(submission[0]) - 1
    status = submission[1]

    if penaltyCount[p] == -1:
        continue
    if status == "WA":
        penaltyCount[p] += 1
    else:
        penalty += penaltyCount[p]
        penaltyCount[p] = -1
        correct += 1

print(str(correct) + " " + str(penalty))
f = input().split()
input()
while True:
    t, s = map(f.index, input().split())
    if t in A and s in A:
        print(f[2]) if A.index(t) - A.index(s) in D else print(f[3])
    if t in B and s in B:
        print(f[0]) if B.index(t) - B.index(s) in D else print(f[5])
    if t in C and s in C:
        print(f[1]) if C.index(t) - C.index(s) in D else print(f[4])

### FIXED CODE ###

R = ((1,2,4,3),(2,0,3,5),(0,1,5,4))
f = input().split()

for i in range(int(input())):
    t, s = map(f.index, input().split())
    for j in R:
        if not (t in j)*(s in j):
            continue
        d = R.index(j)
        if (j.index(t) - j.index(s)) %4 == 1:
            d -= 5
    print(f[abs(d)])
oding: utf-8
 
N  = int(input())
sum = 0
 
for i in range(N):
    if ( i % 3 != 0):
        if (i % 5 != 0):
           sum += i
 
print(sum)

### FIXED CODE ###

#coding: utf-8
 
N  = int(input())
sum = 0
 
for i in range(N+1):
    if ( i % 3 != 0):
        if (i % 5 != 0):
           sum += i
 
print(sum)
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 29 20:53:20 2019

@author: Yamazaki Kenichi
"""
from collections import deque
import sys

N, M = map(int,input().split())
uv = [list(map(int,input().split())) for i in range(N)]
S, T = map(int,input().split())

Ta = [[] for i in range(N+1)]
for c in uv:
    Ta[c[0]].append(c[1])

counta = 0
rout = [[] for i in range(N+1)]
while len(rout[S]) < 3:
    next_ = deque([S])
    for i in range(3):
        for j in range(len(next_)):
            tmp = next_.popleft()
            for k in Ta[tmp]:
                next_.append(k)
            rout[tmp].append(i)
        
        if rout[T].count(2) >= 1:
            print(counta)
            sys.exit()
        counta += 1
print(-1)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Jul  1 11:43:19 2019

@author: Yamazaki Kenichi
"""
from collections import deque

N, M = map(int,input().split())
uv = [list(map(int,input().split())) for i in range(M)]
S, T = map(int,input().split())

Ta = [[] for i in range(3*N+1)]
for c in uv:
    Ta[c[0]].append(c[1]+N)
    Ta[c[0]+N].append(c[1]+2*N)
    Ta[c[0]+2*N].append(c[1])

check = [0 for i in range(3*N+1)]

q = deque([S])
check[S] = 1
counta = 0
flg = False
while len(q) > 0:
    for i in range(len(q)):
        nexts = Ta[q.popleft()]
        for next_ in nexts:
            if check[next_] != 1:
                q.append(next_)
                check[next_] = 1
    counta += 1
    if check[T] == 1:
        flg = True
        break
if flg:
    print(counta//3)
else:
    print(-1)
import sys,math,collections,itertools
input = sys.stdin.readline

N=int(input())
XY = []
xAve = 0
yAve = 0
for _ in range(N):
    x,y=map(int,input().split())
    XY.append([x,y])
    xAve += x
    yAve += y
xAve = xAve/N
yAve = yAve/N
XYnorm = [0]*4

for x,y in XY:
    nX = x-xAve
    nY = y-yAve
    if nX>=0 and nY>=0:#第1象限
        if XYnorm[0]<= nX+nY:
            XYnorm[0] = nX+nY
            XY0 =[x,y]

    if nX <=0 and nY >=0:#第2象限
        if XYnorm[1]<= -nX+nY:
            XYnorm[1] = -nX+nY
            XY1 =[x,y]
            
    if nX <=0 and nY <=0:#第3象限
        if XYnorm[2]<= -nX-nY:
            XYnorm[2] = -nX-nY
            XY2 =[x,y]
            
    if nX >=0 and nY <=0:#第4象限
        if XYnorm[3]<= nX-nY:
            XYnorm[3] = nX-nY
            XY3 =[x,y]

try:
    XY01 = abs(XY0[0]-XY1[0])+abs(XY0[1]-XY1[1])
except:
    XY01=0
    
try:
    XY02 = abs(XY0[0]-XY2[0])+abs(XY0[1]-XY2[1])
except:
    XY02=0
try:
    XY03 = abs(XY0[0]-XY3[0])+abs(XY0[1]-XY3[1])
except:
    XY03=0
try:
    XY12 = abs(XY1[0]-XY2[0])+abs(XY1[1]-XY2[1])
except:
    XY12 = 0
try:
    XY13 = abs(XY1[0]-XY3[0])+abs(XY1[1]-XY3[1])
except:
    XY13 = 0
try:
    XY23 = abs(XY2[0]-XY3[0])+abs(XY2[1]-XY3[1])
except:
    XY23 = 0
print(max([XY01,XY02,XY03,XY12,XY13,XY23])
    


### FIXED CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

N=int(input())
zmax=-float('inf')
zmin = float('inf')
wmax = -float('inf')
wmin = float('inf')

for _ in range(N):
    x,y=map(int,input().split())
    z=x+y
    w=x-y
    zmax = max(z,zmax)
    zmin = min(z,zmin)
    wmax = max(w,wmax)
    wmin = min(w,wmin)
print(max(zmax-zmin,wmax-wmin))
s=input()
t=input()
for i in range(len(s)):
    if [:i]+[i:]==t:
        ans=0
    else:
        ans=1
        break
if ans==0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s=input()
t=input()
for i in range(len(s)):
    if s[i:]+s[:i]!=t:
        ans=0
    else:
        ans=1
        break
if ans==1:
    print("Yes")
else:
    print("No")
import itertools
import math
H,W,A,B=map(int,raw_input().split())

mod=10**9+7


FACT={}
FACT_INVERSE={}

n=1
for i in range(H+W-1):
	if i==0: n=1
	else: n=(n*i)%mod
	FACT[i]=n

#print FACT


def C(n,r):
	return (FACT[n]*pow(FACT[r],10**9+5 ,mod)*pow(FACT[n-r],10**9+5 ,mod)) %mod

N=(H-A-1)+B
M=(H-1)+(W-1)-N

p=0
for i in range(H-A,H):
	#print N,i,M,(H-1)-i,C(N,i), C(M,(H-1)-i)
	p+=C(N,i)*C(M,(H-1)-i)		#Count patterens via prohibited point.
	p=p%mod


if C(N+M,(H-1))-p>=0:
	print C(N+M,(H-1))-p
else:
	print C(N+M,(H-1))-p+10**9+7
    

### FIXED CODE ###

import itertools
import math
H,W,A,B=map(int,raw_input().split())

mod=10**9+7


FACT={}
FACT_INVERSE={}

n=1
for i in range(H+W-1):
	if i==0: n=1
	else: n=(n*i)%mod
	FACT[i]=n

#print FACT

def C(n,r):
	return (FACT[n]*pow(FACT[r],10**9+5 ,mod)*pow(FACT[n-r],10**9+5 ,mod)) %mod


p=0
for i in range(B,W):
	p+=C(H-A-1+i,i)*C(A-1+W-i-1,W-i-1)
	p=p%mod


print p
h,n=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
# ans=1
# for i in range(n):
#     ans+=a[i][0]
M=10**12
dp=[[M for i in range(max(h+10010,2*h+2))] for j in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(n):
    for j in range(max(h+10010,2*h+2)):
        if j<a[i][0]:
            dp[i+1][j]=dp[i][j]
        elif dp[i+1][j-a[i][0]]<M and dp[i][j]<M:
            dp[i+1][j]=min(dp[i][j],dp[i+1][j-a[i][0]]+a[i][1])
        elif dp[i+1][j-a[i][0]]<M:
            dp[i+1][j]=dp[i+1][j-a[i][0]]+a[i][1]
        elif dp[i][j]<M:
            dp[i+1][j]=dp[i][j]
# for i in range(n+1):
#     print(dp[i])
for i in range(h,max(h+10010,2*h+2)):
    if dp[n][i]<M:
        print(dp[n][i])
        exit()

### FIXED CODE ###

h=int(input())
i=0
ans=0
while h>0:
    ans+=(1<<i)
    h//=2
    i+=1
print(ans)
import math

r = int(input())

print('{:.5f} {:.5f}'.format(math.pi*r*r, 2*math.pi*r))


### FIXED CODE ###

import math

r = float(input())
print(math.pi * r ** 2, 2 * math.pi * r)
# 入力
N, X, T = input().split()

if N % X == 0:
    cnt = int(N / X)
else:
    cnt = int(N / X + 1)

print(cnt * T)

### FIXED CODE ###

# 入力
N, X, T = input().split()

N = int(N)
X = int(X)
T = int(T)

if N % X == 0:
    cnt = int(N / X)
else:
    cnt = int(N / X + 1)

print(cnt * T)
a, b, c = map(int, input().split(' '))

if a + b == c:
    print('Yes')
    return
elif a + c == b:
    print('Yes')
    return
elif b + c == a:
    print('Yes')
    return
else:
    print('No')
    return

### FIXED CODE ###

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

if a + b == c:
    print('Yes')

elif a + c == b:
    print('Yes')

elif b + c == a:
    print('Yes')

else:
    print('No')
N=int(input())
s=[sorted(list(input())) for i in range(N)]
s.sort()

counter=long(0)

i=0
while i<N-1:
  j=i+1
  while j<N:
    if s[i]==s[j]:
	    counter+=1
	    j+=1
    else:
      break
    
  i+=1
  
print(counter)

### FIXED CODE ###

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


dic={}
counter=0
for i in range(N):
  if (s[i] in dic.keys())==True:
    counter+=dic[s[i]]
    dic[s[i]]=dic[s[i]]+1
  else:
    dic[s[i]]=1

print(counter)