Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
X = list(map(int, input().split()))
Y = []
Z = []
zc = 0
for i in range(N):
    if X[i] > 0:
        Y.append(X[i])
    if X[i] == 0:
        zc = 1
for i in range(N-1, -1, -1):
    if X[i] < 0:
        Z.append(-X[i])

cs = []
K -= zc
if K == 0:
    print(0)
else:
    if len(Y) >= K:
        cs.append(Y[K-1])
    if len(Z) >= K:
        cs.append(Z[K-1])
    for i in range(K-1):
        cs.append(2*Y[i]+Z[K-i-2])
    for i in range(K-1):
        cs.append(2*Z[i]+Y[K-i-2])
print(min(cs))


Fixed submission:
N, K = map(int, input().split())
X = list(map(int, input().split()))
Y = []
Z = []
zc = 0
for i in range(N):
    if X[i] > 0:
        Y.append(X[i])
    if X[i] == 0:
        zc = 1
for i in range(N-1, -1, -1):
    if X[i] < 0:
        Z.append(-X[i])

cs = []
K -= zc
if K == 0:
    print(0)
else:
    if len(Y) >= K:
        cs.append(Y[K-1])
    if len(Z) >= K:
        cs.append(Z[K-1])
    for i in range(min(K-1, len(Y))):
        if K-i-2 < len(Z):
            cs.append(2*Y[i]+Z[K-i-2])
    for i in range(min(K-1, len(Z))):
        if K-i-2 < len(Y):
            cs.append(2*Z[i]+Y[K-i-2])
    print(min(cs))
Buggy python submission (verdict: Runtime Error):
s =  int(input())
k =  int(input())
#print(pow(10, 12))
def main(string_s):
    if str(s).lstrip('1')[0] == '2':
        print('2')
    elif str(s).lstrip('1')[0] == '3':
        print('3')
    elif str(s).lstrip('1')[0] == '4':
        print('4')
    elif str(s).lstrip('1')[0] == '5':
        print('5')
    elif str(s).lstrip('1')[0] == '6':
        print('6')
    elif str(s).lstrip('1')[0] == '7':
        print('7')
    elif str(s).lstrip('1')[0] == '8':
        print('8')
    elif str(s).lstrip('1')[0] == '9':
        print('9')
    else:
        print('1')

main(s)


Fixed submission:
s =  int(input())
k =  int(input())
#print(pow(10, 12))
def main(string_s):
    for i, j in enumerate(str(string_s)):
#        print(i, j)
#        print(i, k)
        if j != '1':
            break
        if i+1 == k:
            print('1')
            return
    if str(s).lstrip('1') == '':
         print('1')
         return
    if str(s).lstrip('1')[0] == '2':
        print('2')
    elif str(s).lstrip('1')[0] == '3':
        print('3')
    elif str(s).lstrip('1')[0] == '4':
        print('4')
    elif str(s).lstrip('1')[0] == '5':
        print('5')
    elif str(s).lstrip('1')[0] == '6':
        print('6')
    elif str(s).lstrip('1')[0] == '7':
        print('7')
    elif str(s).lstrip('1')[0] == '8':
        print('8')
    elif str(s).lstrip('1')[0] == '9':
        print('9')
    else:
        print('1')

main(s)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
n,m = [int(a) for a in input().strip().split(' ')]
As = accumulate([int(a)%m for a in input().strip().split(' ')])
As = [0] + [i%m for i in As]

def isok(i,j):
    di = As[j] - As[i-1]
    if di % m == 0:
        return True
    return False


counter = 0
for i in range(n):
    for j in range(i, n):
        di = As[j+1] - As[i]
        if di % m == 0:
            counter += 1
print(counter)


Fixed submission:
from itertools import accumulate
n,m = [int(a) for a in input().strip().split(' ')]
As = accumulate([int(a)%m for a in input().strip().split(' ')])
As = [0] + [i%m for i in As]
As = sorted(As)
count = 0
ba = None
Bs = []
for a in As:
    if a == ba:
        count += 1
    elif ba != None:
        Bs.append(count*(count+1))
        count = 0
    ba = a
if count != 0:
    Bs.append(count*(count+1))
print(int(sum(Bs)/2))

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
n,m = [int(a) for a in input().strip().split(' ')]
As = accumulate([int(a)%m for a in input().strip().split(' ')])
As = [0] + [i%m for i in As]

def isok(i,j):
    di = As[j] - As[i-1]
    if di % m == 0:
        return True
    else:
        return False


counter = 0
for i in range(n):
    for j in range(i, n):
        if isok(i+1, j+1):
            counter += 1
print(counter)


Fixed submission:
from itertools import accumulate
n,m = [int(a) for a in input().strip().split(' ')]
As = accumulate([int(a)%m for a in input().strip().split(' ')])
As = [0] + [i%m for i in As]
As = sorted(As)
count = 0
ba = None
Bs = []
for a in As:
    if a == ba:
        count += 1
    elif ba != None:
        Bs.append(count*(count+1))
        count = 0
    ba = a
if count != 0:
    Bs.append(count*(count+1))
print(int(sum(Bs)/2))

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
n,m = [int(a) for a in input().strip().split(' ')]
As = [0] + list(accumulate([int(a)%m for a in input().strip().split(' ')]))

def isok(i,j):
    di = As[j] - As[i-1]
    if di % m == 0:
        return True
    else:
        return False


counter = 0
for i in range(n):
    for j in range(i, n):
        if isok(i+1, j+1):
            counter += 1
print(counter)


Fixed submission:
from itertools import accumulate
n,m = [int(a) for a in input().strip().split(' ')]
As = accumulate([int(a)%m for a in input().strip().split(' ')])
As = [0] + [i%m for i in As]
As = sorted(As)
count = 0
ba = None
Bs = []
for a in As:
    if a == ba:
        count += 1
    elif ba != None:
        Bs.append(count*(count+1))
        count = 0
    ba = a
if count != 0:
    Bs.append(count*(count+1))
print(int(sum(Bs)/2))
Buggy python submission (verdict: Runtime Error):
import random
from itertools import accumulate
N = int(input())
As = [int(i) for i in input().split(' ')]

#N = pow(10, 4)
#As = [random.randint(0,1000) for r in range(N)] 
As = list(accumulate(As))


def bsearch(l, ls, rs):
    n = int(len(l)/2)
    if n == 0:
        return [max(l[0]-ls , rs-l[0]), min(l[0]-ls , rs-l[0])]
    lsum = l[n] - ls
    rsum = rs - l[n]
    ll = l[:n]
    rl = l[n:]
    if lsum > rsum:
        return bsearch(ll, ls, rs)
    else:
        return bsearch(rl, ls, rs)

for i in range(N-3):
    cs = bsearch(As[:i+2], 0, As[i+1]) + bsearch(As[i+2:], As[i+1], As[-1])
    if i == 0:
        result = max(cs) - min(cs)
    else:
        if max(cs) - min(cs) < result:
            result = max(cs) - min(cs)
print(result)


Fixed submission:
N = int(input())
As = sorted([int(a)-i for i, a in enumerate(input().strip().split(' '))])

temp1 = 0
temp2 = sum(As)
for i, a in enumerate(As):
    temp1 += As[i]
    temp2 -= As[i]
    r = As[i] * (i+1) - temp1 +\
    temp2 - As[i] * (N-1-i)
    result = min(result, r) if i != 0 else r
print(result)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
As = sorted([int(a)-i for i, a in enumerate(input().strip().split(' '))])

for i, a in enumerate(As):
    temp = min(temp, -1 * sum([x-As[i] for x in As[:i]]) + sum([x-As[i] for x in As[i:]])) if i!= 0 else -1 * sum([x-As[i] for x in As[:i]]) + sum([x-As[i] for x in As[i:]])
print(temp)


Fixed submission:
N = int(input())
As = sorted([int(a)-i for i, a in enumerate(input().strip().split(' '))])

temp1 = 0
temp2 = sum(As)
for i, a in enumerate(As):
    temp1 += As[i]
    temp2 -= As[i]
    r = As[i] * (i+1) - temp1 +\
    temp2 - As[i] * (N-1-i)
    result = min(result, r) if i != 0 else r
print(result)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
As = [int(i) for i in input().split(' ')]


def bsearch(l, lsum, rsum):
    n = int(len(l)/2)
    if n == 0:
        return [max(rsum, lsum) , min(rsum, lsum) + l[0]]
    ll = l[:n]
    rl = l[n:]
    llsum = sum(ll)
    rrsum = sum(rl)
    lsum += llsum
    rsum += rrsum
    if lsum > rsum:
        return bsearch(ll, lsum-llsum, rsum)
    else:
        return bsearch(rl, lsum, rsum-rrsum)

for i in range(N-3):
    cs = bsearch(As[:i+2], 0, 0) + bsearch(As[i+2:], 0, 0)
    if i == 0:
        result = max(cs) - min(cs)
    else:
        if max(cs) - min(cs) < result:
            result = max(cs) - min(cs)
print(result)


Fixed submission:
import random
from itertools import accumulate
N = int(input())
As = [int(i) for i in input().split(' ')]

#N = pow(10, 4)
#As = [random.randint(0,1000) for r in range(N)] 
As = list(accumulate(As))


def bsearch(L, l, r, ls, rs):
    if r - l == 0:
        l_temp = L[l-1] if l!=0 else 0
        lsum = l_temp - ls
        return [max(lsum, rs - L[l]), min(lsum, rs - L[l]) + L[l] - l_temp]
    n = int((r-l)/2)
    lsum = L[l+n] - ls
    rsum = rs - L[l+n]
    if lsum > rsum:
        return bsearch(L, l, l+n, ls, rs)
    else:
        return bsearch(L, l+n+1, r, ls, rs)

for i in range(N-3):
    cs = bsearch(As, 0, i+1, 0, As[i+1]) + bsearch(As ,i+2, N-1, As[i+1], As[-1])
    if i == 0:
        result = max(cs) - min(cs)
    else:
        if max(cs) - min(cs) < result:
            result = max(cs) - min(cs)
print(result)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
xs = [[] for _ in range(N)]
for j in range(N):
    a, b, c = map(int, input().split())
    for i in range(2**3):
        t = []
        for k in range(3):
            t.append(1-2*((i>>k)%2))
        xs[i].append(a*t[0] +b*t[1]+c*t[2])
print(max(sum(sorted(xs[i])[-M:]) for i in range(2**3)))


Fixed submission:
N, M = map(int, input().split())
xs = [[] for _ in range(8)]
for j in range(N):
    a, b, c = map(int, input().split())
    for i in range(2**3):
        t = []
        for k in range(3):
            t.append(1-2*((i>>k)%2))
        xs[i].append(a*t[0] +b*t[1]+c*t[2])
print(max(sum(sorted(xs[i])[-M:]) for i in range(2**3))*(M!=0))
Buggy python submission (verdict: Runtime Error):
N, K, Q = map(int, input().split())
X = list(map(int, input().split()))

r = Y[Q-1] - Y[0]
for y in X:
    tmp = []
    tmp2 = []
    for x in X:
        if x < y:
            tmp.sort()
            tn = len(tmp)
            if len(tmp) > K-1:
                tmp2 += tmp[:tn-K+1]
                print(tmp, tmp[:tn-K+1])
            tmp = []
            continue
        tmp.append(x)
    tn = len(tmp)
    if tn-K+1 > 0:
        tmp2 += tmp[:tn-K+1]
    tmp2.sort()
    if len(tmp2) >= Q:
        r = min(r, tmp2[Q-1] - y)
print(r)


Fixed submission:
N, K, Q = map(int, input().split())
X = list(map(int, input().split()))

r = 10**18
for y in X:
    tmp = []
    tmp2 = []
    for x in X:
        if x < y:
            tmp.sort()
            tn = len(tmp)
            if len(tmp) > K-1:
                tmp2 += tmp[:tn-K+1]
            tmp = []
            continue
        tmp.append(x)
    tmp.sort()
    tn = len(tmp)
    if tn-K+1 > 0:
        tmp2 += tmp[:tn-K+1]
    tmp2.sort()
    if len(tmp2) >= Q:
        r = min(r, tmp2[Q-1] - y)
print(r)
Buggy python submission (verdict: Runtime Error):
a, b, _, k = [int(i) for x in input().strip().split(" ")]

if k % 2 == 0:
    print(a-b)
else:
    print(b-a)


Fixed submission:
a, b, _, k = [int(x) for x in input().strip().split(" ")]

if k % 2 == 0:
    print(a-b)
else:
    print(b-a)
Buggy python submission (verdict: Runtime Error):
def sub_k(string, I, K):
    temp = []
    for i in range(len(string)):
        if i-1+I == len(string):
            continue
        temp.append(string[i:i+I])
    return sorted(set(temp))[0:K]

def main(string, K):
    result = []
    for i in range(K):
        result += sub_k(string, i+1, K-i)
    print(sorted(set(result))[K-1])

string = input()
K = int(input())
main(string, K)

Fixed submission:
def sub_k(string, I, K):
    temp = []
    for i in range(len(string)):
        if i-1+I == len(string):
            break
        temp.append(string[i:i+I])
    return sorted(set(temp))[0:K]

def main(string, K):
    result = []
    for i in range(K):
        result += sub_k(string, i+1, K-i)
    print(sorted(set(result))[K-1])

string = input()
K = int(input())
main(string, K)

Buggy python submission (verdict: Runtime Error):
def sub_k(string, I, K):
    temp = []
    for i in range(len(string)):
        if i-1+I == len(string):
            continue
        temp.append(string[i:i+I])
    return sorted(set(temp))[0:K]

def main(string, K):
    for i in range(K):
        print(sub_k(string, i+1, K-i))

string = input()
K = input()
main(string, K)

Fixed submission:
def sub_k(string, I, K):
    temp = []
    for i in range(len(string)):
        if i-1+I == len(string):
            break
        temp.append(string[i:i+I])
    return sorted(set(temp))[0:K]

def main(string, K):
    result = []
    for i in range(K):
        result += sub_k(string, i+1, K-i)
    print(sorted(set(result))[K-1])

string = input()
K = int(input())
main(string, K)
Buggy python submission (verdict: Runtime Error):
N, = map(int, input().split())
X = set(map(int, input().split()))
if len(X) == 3:
    print("Three")
else:
    print("Four")


Fixed submission:
N, = map(int, input().split())
X = set(map(str, input().split()))
if len(X) == 3:
    print("Three")
else:
    print("Four")
Buggy python submission (verdict: Runtime Error):
if (a*b%2):
 print("Odd")
else:
 print("Even")

Fixed submission:
a, b  = map(int, input().split())
if (a*b%2):
 print("Odd")
else:
 print("Even")
Buggy python submission (verdict: Runtime Error):
N, = map(int, input().split())
A = map(int, input().split())
from collections import defaultdict
d = defaultdict(int)
for a in A:
    d[a] += 1
r = 0
for a in d:
    if a > d[a]:
        r += d[a]
    else:
        r += d[a]-a
print(r)


Fixed submission:
N, K = map(int, input().split())
X = map(int, input().split())
from collections import defaultdict
d = defaultdict(int)
for x in X:
    d[x] += 1

l = sorted(list(d.values()))
print(sum(l[:max(0, len(l)-K)]))
Buggy python submission (verdict: Runtime Error):
N, Y, Z = map(int, input().split())
As = list(map(int, input().split()))
dpx, dpy = [0]*(N-1), [0]*(N-1)
#dpx[i] = min(dpy[i+1]...dpy[N-2], abs(As[N-1]-As[i]))
#dpy[i] = max(dpx[i+1]...dpx[N-2], abs(As[N-1]-As[i]))
for i in range(N-2, -1, -1):
    mny, mxx = 10**10, 0
    for j in range(i+1, N-1):
        mny = min(mny, dpy[j])
        mxx = max(mxx, dpx[j])
    dpx[i] = min(mny, abs(As[N-1]-As[i]))
    dpy[i] = min(mxx, abs(As[N-1]-As[i]))
#print(dpx)
print(max(max(dpx),abs(As[N-1]-Z)))


Fixed submission:
N, Y, Z = map(int, input().split())
As = list(map(int, input().split()))
dpx, dpy = [0]*(N-1), [0]*(N-1)
#dpx[i] = min(dpy[i+1]...dpy[N-2], abs(As[N-1]-As[i]))
#dpy[i] = max(dpx[i+1]...dpx[N-2], abs(As[N-1]-As[i]))
for i in range(N-2, -1, -1):
    mny, mxx = 10**10, 0
    for j in range(i+1, N-1):
        mny = min(mny, dpy[j])
        mxx = max(mxx, dpx[j])
    dpx[i] = min(mny, abs(As[N-1]-As[i]))
    dpy[i] = max(mxx, abs(As[N-1]-As[i]))
dpx.append(abs(As[N-1]-Z))
print(max(dpx))
Buggy python submission (verdict: Runtime Error):
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

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

NNN = (10**5)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N, = map(int, input().split())
ps = list(map(int, input().split()))
p2i = dict()
i = 0
for p in ps:
    if p not in p2i:
        i += 1
        p2i[p] = i
        continue
    x = p2i[p]
    break
X = min(x-1, i-1)
Y = min(N-x, N-i)
for i in range(1, N+2):
    print((cmb(N+1, i) - cmb(X+Y, i-1))%mod)


Fixed submission:
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

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

NNN = (2*10**5)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N, = map(int, input().split())
ps = list(map(int, input().split()))
p2i = dict()
i = 0
for p in ps:
    if p not in p2i:
        i += 1
        p2i[p] = i
        continue
    x = p2i[p]
    break
X = min(x-1, i-1)
Y = min(N-x, N-i)
for i in range(1, N+2):
    print((cmb(N+1, i) - cmb(X+Y, i-1))%mod)
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())

mnr = 10**9
for a in range(1, W//2 + 1):
    b1 = (H*W)//(a + W)
    b2 = b1+1
    mc = max(abs((W-a)*b1-a*b1), abs(b1*(a+W) - H*W))
    mc2 = max(abs((W-a)*b2-a*b2), abs(b2*(a+W) - H*W))
    mnr = min([mnr, mc, mc2])
H, W = W, H
for a in range(1, W//2 + 1):
    b1 = (H*W)//(a + W)
    b2 = b1+1
    mc = max(abs((W-a)*b1-a*b1), abs(b1*(a+W) - H*W))
    mc2 = max(abs((W-a)*b2-a*b2), abs(b2*(a+W) - H*W))
    mnr = min([mnr, mc, mc2])
if H % 3 == 0 or W % 3== 0:
    mnr = 0
elif H % 3:
    mnr = min(W, mnr)
else:
    mnr = min(H, mnr)
print(mnr)


Fixed submission:
# ABC140E
class SegTree:
    def __init__(self, init_val, ide_ele, seg_func):
        self.segfunc = seg_func
        N = len(init_val)
        self.num = 2**(N-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(N):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
N, = map(int, input().split())
A = list(map(int, input().split()))
B = sorted([(a, i) for i, a in enumerate(A)], key=lambda x:x[0])
z = dict()
for i, (b, j) in enumerate(B):
    z[(b, j)] = i

ss = SegTree([3*N]*3*N, 3*N, min)
bs = []
y = 0
for i, x in enumerate(A):
    if i == 2*N:
        break
    ss.update(z[(x, i)], z[(x, i)])
    y += x
    if i < N-1:
        continue
    if i == N-1:
        bs.append(y)
    else:
        mx = ss.query(0, 3*N)
        y = y - B[mx][0]
        ss.update(mx, 3*N)
        bs.append(y)

ss = SegTree([-1]*3*N, -1, max)
nbs = []
#tmp = set()
y = 0
for i, x in enumerate(A[::-1]):
    if i == 2*N:
        break
    ss.update(z[(x, 3*N-i-1)], z[(x, 3*N-i-1)])
#    tmp.add((x, i))
    y += x
    if i < N-1:
        continue
    if i == N-1:
        nbs.append(y)
    else:
        mx = ss.query(0, 3*N)
#        print(max(tmp), B[mx])
#        tmp.remove(max(tmp))
        y = y - B[mx][0]
        ss.update(mx, -1)
        nbs.append(y)

#print(B)
#print(bs)
#print(nbs)
r = -10**18
for i in range(N+1):
    r = max(r, bs[i] - nbs[N-i])
print(r)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [a for a in A if a <K]
N = len(A)
dp2 = [1] + [0]*K
dpm = [[0]*(K+1) for _ in range(N+1)]
dpm[0][0] = 1
for i, a in enumerate(A):
    for j in range(K, -1, -1):
        dpm[i+1][j] = dpm[i][max(0, j-a)] + dpm[i][j]
#print(dpm)

r = 0
for i, a in enumerate(A[::-1]):
    f = True
    for j in range(K, -1, -1):
        # 後ろiこの合計がjのもの
        if f and dp2[j] > 0:
            # K-j > x >= K-j-a
            if dpm[N-i-1][max(0, K-j-a)] > dpm[N-i-1][K-j]:
                f = False
        if j-a>=0:
            dp2[j] = dp2[j] + dp2[j-a]
    if f:
        r += 1
#    for j in range(K-1, 0, -1):
#        print("aa", i, N-i-1)
print(r)


Fixed submission:
x = int(input())
for i in range(1, 10**5):
    if x <= i*(i+1)//2:
        break
print(i)
Buggy python submission (verdict: Runtime Error):
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

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

NNN = (10**5)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
H, W, A, B = map(int, input().split())

r = 0
for i in range(H-A):
#    (0, 0) -> (i, B-1)
#    (i, B) -> (H-1, W-1)
    r = (r + mul(cmb(i+B-1, i), cmb(H-1-i+W-1-B, H-1-i)))%mod
print(r)



Fixed submission:
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

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

NNN = (10**6)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
H, W, A, B = map(int, input().split())

r = 0
for i in range(H-A):
#    (0, 0) -> (i, B-1)
#    (i, B) -> (H-1, W-1)
    r = (r + mul(cmb(i+B-1, i), cmb(H-1-i+W-1-B, H-1-i)))%mod
print(r)
Buggy python submission (verdict: Runtime Error):
N, x = map(int, input().split())
arr = list(map(int, input().split()))

arr.sort()
cnt = 0
for ele in arr:
    if x < ele:
        break
    x -= ele
    cnt += 1

if cnt = N and x > 0:
    cnt -= 1

print(cnt)

Fixed submission:
N, x = map(int, input().split())
arr = list(map(int, input().split()))

arr.sort()
cnt = 0
for ele in arr:
    if x < ele:
        break
    x -= ele
    cnt += 1

if cnt == N and x > 0:
    cnt -= 1

print(cnt)

Buggy python submission (verdict: Runtime Error):
N, x = map(int, input().split())
arr = list(map(int, input().split()))

arr.sort()
cnt = 0
for ele in arr:
    if x < ele:
        break
    x -= ele
    cnt += 1

if cnt = N and x != 0:
    cnt -= 1

print(cnt)


Fixed submission:
N, x = map(int, input().split())
arr = list(map(int, input().split()))

arr.sort()
cnt = 0
for ele in arr:
    if x < ele:
        break
    x -= ele
    cnt += 1

if cnt == N and x > 0:
    cnt -= 1

print(cnt)
Buggy python submission (verdict: Runtime Error):
N = int(input())
ans = "Yes"
arr = []
for i in range(N)
    arr.append(input())
    if not i == 1:
        if arr[i] in arr and arr[i-1][-1] == arr[i][0]
            pass
        else:
            ans = "No"
            break

print(ans)


Fixed submission:
N = int(input())
ans = "Yes"
arr = []
for i in range(N):
    arr.append(input())
    if not i == 0:
        if arr[i-1][-1] == arr[i][0] and not arr[i] in arr[:-2]:
            pass
        else:
            ans = "No"
            break

print(ans)
Buggy python submission (verdict: Runtime Error):
s = str(input())
t = str(input())

sd = sorted(s)
td = sorted(t, reverse=True)

ans = "No"
for i in range(len(sd)):
    if td[i] > sd[i]:
        ans = "Yes"
        break
    elif td[i] == sd[i]:
        pass
    else:
        break;

print(ans)


Fixed submission:
s = str(input())
s_asc = ''.join(sorted(s))

t = str(input())
t_desc = ''.join(sorted(t, reverse=True))

if t_desc > s_asc:
    print("Yes")
else:
    print("No")