Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import heapq
N,M = map(int,input().split())
list_A = list(map(lambda x: int(x)*(-1),input().split()))	

#print(list_A)

for i in range(M):
  heapq.heapify(list_A)
  target = heapq.heappop(list_A)
  #print("after heappop",list_A)
  
  '''負の要素の切り捨て除算は切り捨てがマイナスの方に
  行くため少しだけややこしい。'''
  target = -1*((-1 *target) // 2)
  
  heapq.heappush(list_A, target)  # 要素の挿入
  #print("No.",i,"change finished",list_A)

print(sum(list_A)*-1)




### FIXED CODE ###

import heapq
N,M = map(int,input().split())
list_A = list(map(lambda x: int(x)*(-1),input().split()))	

#print(list_A)
heapq.heapify(list_A)
for i in range(M):
  
  target = heapq.heappop(list_A)
  #print("after heappop",list_A)
  
  '''負の要素の切り捨て除算は切り捨てがマイナスの方に
  行くため少しだけややこしい。'''
  heapq.heappush(list_A, (-1)*((-target) // 2))  # 要素の挿入
  #print("No.",i,"change finished",list_A)

print(-sum(list_A))
### BUGGY CODE ###

s = list(input())
q = int(input())

inn = []
jun = 0

for i in range(q):
    inn = list(input().split())
    if inn[0] == "1":
        if jun == 0:
            jun = 1
        else:
            jun = 0#jun = 0はそのまま　jun = 1は逆をする
    elif inn[0] == "2":
        if inn[1] == "1" and jun == 0:
            s.insert(0,inn[2])
        elif inn[1] == "2" and jun == 0:
            s.append(inn[2])
        if inn[1] == "1" and jun == 1:
            s.append(inn[2])
        elif inn[1] == "2" and jun == 1:
            s.insert(0,inn[2])
        
if jun == 0:
    news = ''.join(s)
else:
    s = s[::-1]
    news = ''.join(s)

print(news)
               

### FIXED CODE ###

import collections

s = list(input())
q = int(input())

s2 = collections.deque(s)

inn = []
jun = 0

for i in range(q):
    inn = list(input().split())
    if inn[0] == "1":
        if jun == 0:
            jun = 1
        else:
            jun = 0#jun = 0はそのまま　jun = 1は逆をする
    elif inn[0] == "2":
        if inn[1] == "1" and jun == 0:
            s2.appendleft(inn[2])
        elif inn[1] == "2" and jun == 0:
            s2.append(inn[2])
        if inn[1] == "1" and jun == 1:
            s2.append(inn[2])
        elif inn[1] == "2" and jun == 1:
            s2.appendleft(inn[2])
    
if jun == 0:
    news = ''.join(s2)
else:
    s2.reverse()
    news = ''.join(s2)

print(news)
### BUGGY CODE ###

def main():
    from heapq import heappush, heappop
    from operator import itemgetter

    n = int(input())
    a = [[int(x) for x in input().split()] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if a[i][j] != min(a[i][k] + a[k][j] for k in range(n)):
                print(-1)
                return

    h = []
    for r, row in enumerate(a):
        for c, cell in enumerate(row):
            if r == c: break
            bit = (1 << r) | (1 << c)
            heappush(h, (cell, bit))  # dist,bit

    pathes = set()
    while h:
        dist, bit = heappop(h)

        is_path = True
        for d1, p1 in pathes:
            for d2, p2 in pathes:
                xor = p1 ^ p2
                if (xor == bit) and (dist >= d1 + d2):
                    is_path = False
                    break
            if not is_path:
                break

        if is_path:
            pathes.add((dist, bit))

    print(sum(map(itemgetter(0), pathes)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

INF = 10 ** 12

N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]

for i in range(N):
    for j in range(N):
        for k in range(N):
            if a[i][j] > a[i][k] + a[k][j]:
                print(-1)
                exit()

res = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if i != k and j != k and a[i][j] == a[i][k] + a[k][j]:
                break
        else:
            res += a[i][j]

print(res)
### BUGGY CODE ###

def check(r,c):
    flag = True
    for ri,rj in enumerate(B):
        for ci,cj in enumerate(rj):
            if not A[ri+r][ci+c] == cj:
                flag = False
                break
    return flag

H,W = [int(i) for i in input().split()]
A = [input() for _ in range(H)]
R,C = [int(i) for i in input().split()]
B = [input() for _ in range(R)]

for r in range(H-R+1):
    for c in range(W-C+1):
        if check(r,c):
            print(r,c)


### FIXED CODE ###

from collections import deque
import re
import sys
sys.setrecursionlimit(100000)

class AC:
    
    def __init__(self,num,parent,char):
        self.num = num
        self.parent = parent
        self.char = char
        self.d = {}
        self.failure = None
        
    def insert(self,string,num):
        if not string[0] in self.d:
            self.d[string[0]] = AC(num,self,string[0])
            num+=1
        if not string[1:] == "":
            return self.d[string[0]].insert(string[1:],num)
        else:
            return num
        
    def setFailure(self):
        tmp = self.parent.failure
        while(True):
            if self.char in tmp.d:
                self.failure = tmp.d[self.char]
                break
            else:
                if tmp.num == 0:
                    self.failure = tmp
                    break
                else:
                    tmp = tmp.failure
    
    def setFailureRoot(self):
        self.failure = self
    
    def setFailureFirstLayer(self):
        self.failure = self.parent
       
    def transition(self,string):
        if string == "":
            return []
        elif string[0] in self.d:
            tmp = self.d[string[0]]
            num = "{0:09d}".format(tmp.num) 
            return [num]+tmp.transition(string[1:])
        else:
            if self.num == 0:
                num = "{0:09d}".format(self.num)
                return [num]+self.transition(string[1:])
            else:
                return self.failure.transition(string)
    
H,W = [int(i) for i in input().split()]
A = [input() for _ in range(H)]
R,C = [int(i) for i in input().split()]
B = [input() for _ in range(R)]

root = AC(0,None,"")
root.setFailureRoot()
num=1
for i in B:
    num = root.insert(i,num)
d = deque()
for i in root.d.values():
    i.setFailureFirstLayer()
    for j in i.d.values():
        d.appendleft(j)
while(len(d)>0):
    tmp = d.pop()
    tmp.setFailure()
    for i in tmp.d.values():
        d.appendleft(i)
        
trans = ["" for i in range(W)]
for i in A:
    tmp = root.transition(i)
    for j,k in enumerate(tmp):
        trans[j] = trans[j]+k+"#"

ans=""
for i in B:
    ans = ans+root.transition(i)[-1]+"#"

ansd = deque()
for i,j in enumerate(trans):
    obj = re.search(ans,j)
    c = 0
    while(obj):
        s = obj.start()
        if (i-C+1)<0:
            print(i)
        ansd.append(((c+s)//10,i-C+1))
        obj = re.search(ans,j[c+s+10:])
        c += s+10

for i in sorted(ansd):
    print(i[0],i[1])
### BUGGY CODE ###

s = input().strip()
t = input().strip()
ls = len(s)
lt = len(t)

dp = [[0]*(lt+1) for i in range(ls+1)]

for i in range(ls):
    for j in range(lt):
        v = dp[i][j]+1 if s[i] == t[j] else 0
        dp[i+1][j+1] = max([v, dp[i+1][j], dp[i][j+1]])

ans = ''
i, j = ls, lt
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1]+ans
        i -= 1
        j -= 1

print(ans)

### FIXED CODE ###

s = input().strip()
t = input().strip()
ls = len(s)
lt = len(t)

dp = [[0]*(lt+1) for i in range(ls+1)]

for i in range(ls):
    for j in range(lt):
        v = dp[i][j]+1 if s[i] == t[j] else 0
        dp[i+1][j+1] = max([v, dp[i+1][j], dp[i][j+1]])

ans = ''
i, j = ls, lt
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1]+ans
        i -= 1
        j -= 1

print(ans)
### BUGGY CODE ###

n = int(input())
a = map(int,input().split())
t = 1
 
for i in a:
  t *= i
 
if t >10**18:
  print("-1")
else:
  print(str(t))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
t = 1
 
for i in range(len(a)):
  t *= a[i]
  if t > 10**18:
    break
 
if t > 10**18 :
  print("-1")
else:
  print(str(t))
### BUGGY CODE ###

#エラストテネスのふるいを用いることを考える
#出たものの倍数をいれるダメリストを準備しておく。
#各a[i]についてダメリストに入っていないものが求める個数である
#同じものが複数回出てくるもの（Counterを使えばいい）に関してはダメリストにその数もいれれば良い
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
a.sort()
min_a=a[0]
max_a=a[n-1]
#同じものが複数回出てくるもののcheck
dic=Counter(a)
#別リスト
check=[]

for i in range(n):
  if a[i] not in check:
    if dic[a[i]]>=2:
      check.append(a[i])
    for j in range(2,int((max_a)/a[i])+1):
      check.append(a[i]*j)
ans=0
for i in range(n):
  if a[i] not in check:
    ans=ans+1

print(ans)

  
    
    

### FIXED CODE ###

#エラストテネスのふるいを用いることを考える
#出たものの倍数をいれるダメリストを準備しておく。
#各a[i]についてダメリストに入っていないものが求める個数である
#同じものが複数回出てくるもの（Counterを使えばいい）に関してはダメリストにその数もいれれば良い
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
a.sort()
min_a=a[0]
max_a=a[n-1]
#同じものが複数回出てくるもののcheck
dic=Counter(a)
#別リスト
check=set()

for i in range(n):
  if a[i] not in check:
    if dic[a[i]]>=2:
      check.add(a[i])
    for j in range(2,int((max_a)/a[i])+1):
      check.add(a[i]*j)
ans=0
for i in range(n):
  if a[i] not in check:
    ans=ans+1

print(ans)
### BUGGY CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

from collections import deque

N,K = II()
p = III()
x = [(p0+1)/2 for p0 in p]

d = deque(x[:K])
ans = sum(d)
for i in range(K,N):
    d.popleft()
    d.append(x[i])
    now = sum(d)
    if now>ans:
        ans = now

print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

from collections import deque

N,K = II()
p = III()
x = [(p0+1)/2 for p0 in p]

d = deque(x[:K])
ans = sum(d)
now = sum(d)
for i in range(K,N):
    now = now-x[i-K]+x[i]
    if now>ans:
        ans = now

print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N, K, Q = map(int, input().split())
    # A = [int(input()) for _ in range(Q)]
    # print(N, K, Q, A)
    P = [K] * N
    for q in range(Q):
        a = int(input())
        P[a - 1] += 1
        for i in range(N):
            if P[i] < 0:
                continue
            else:
                P[i] -= 1

    for p in P:
        if p > 0:
            print('Yes')
        else:
            print('No')


if __name__ == "__main__":
    main()


### FIXED CODE ###

# #!/usr/bin/env python3
# # -*- coding: utf-8 -*-
import numpy as np


def main():
    N, K, Q = map(int, input().split())
    result = np.array([K - Q] * N)
    for _ in range(Q):
        a = int(input())
        result[a - 1] += 1

    for r in result:
        print('Yes'if r > 0 else 'No')


if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
a = input().split()
output = ''
for i in range(1, n+1):
    output += str(a.index(str(i))+1)
    output += ' '
print(output)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [0]*n
output = ''
for i in range(n):
    b[a[i]-1] = i+1
for i in range(n):
    output += str(b[i]) + ' '
print(output)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for i in range(q):
    l, r = map(int, input().split())
    print(s[l - 1:r].count('AC'))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
x = [0] * (n + 1)
for i in range(n):
    x[i + 1] = x[i] + 1 * (s[i:i + 2] == 'AC')
for i in range(q):
    l, r = map(int, input().split())
    print(x[r - 1] - x[l - 1])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))[::-1]
calc = 0
op = 1

for a in A :
    if op == 1 :
        calc += a
        op = -1
    else :
        calc -= a
        op = 1

for i in range(calc+1) :
    if i == calc-i :
        p = i
        break

X = [p]
op = -1
for a in A[::-1] :
    calc = a - X[-1]
    X.append(calc)

for i in range(len(X)) :
    X[i] *= 2
print(*X[:-1])



### FIXED CODE ###

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

calc = 0

for i in range(0,len(A),2) :
    calc += A[i]
for i in range(1,len(A),2) :
    calc -= A[i]

p = calc//2

X = [0 for i in range(N)]
X[0] = p

for i in range(1,len(X)) :
    X[i] = A[i-1] - X[i-1]

ans = [x*2 for x in X]
print(*ans)
### BUGGY CODE ###

N,M = list(map(int,input().split()))
LR = [list(map(int,input().split())) for i in range(M)]
elements = []
sets = {}

for i in range(M):
  ilist = []
  for j in range(LR[i][1]-LR[i][0]+1):
    ilist.append(LR[i][0]+j)
  elements.append(ilist)
  if i != 0:
    sets = sets & set(elements[i])
  else:
    sets = set(elements[i])

print(len(list(sets)))


### FIXED CODE ###

N, M = map(int,input().split())
L = []
R = []
for i in range(M):
  l, r = map(int,input().split())
  L.append(l)
  R.append(r)

max_l = max(L)
min_r = min(R)
print(max(min_r - max_l + 1, 0))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Feb 24 22:10:01 2019

@author: Yamazaki Kenichi
"""
import bisect
import numpy as np

A,B,Q = map(int,input().split())
s = np.array([int(input()) for i in range(A)])
t = np.array([int(input()) for i in range(B)])
x = np.array([int(input()) for i in range(Q)])

def lr(s,c,A):
#    si = bisect.bisect(s,c)
    si = np.searchsorted(s,c)
    if si == A:
        return [c-s[si-1], 10**11]
    elif si == 0:
        return [10**11, s[0]-c]
    else:
        return [c-s[si-1], s[si]-c]
for c in x:
    ans = 0
    slr = lr(s,c,A)
    tlr = lr(t,c,B)
    ans = min(max(slr[0],tlr[0]),
              max(slr[1],tlr[1]),
              slr[0]*2+ tlr[1],
              slr[0]+ tlr[1]*2,
              slr[1]*2 + tlr[0],
              slr[1]+ tlr[0]*2
              )
    print(ans)
    

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Feb 24 22:10:01 2019

@author: Yamazaki Kenichi
"""
import numpy as np
import bisect

A,B,Q = map(int,input().split())
s = [int(input()) for i in range(A)]
t = [int(input()) for i in range(B)]
x = [int(input()) for i in range(Q)]

def lr(s,c,A):
    si = bisect.bisect(s,c)
    if si == A:
        return [c-s[si-1], 10**11]
    elif si == 0:
        return [10**11, s[0]-c]
    else:
        return [c-s[si-1], s[si]-c]
for c in x:
    ans = 0
    slr = lr(s,c,A)
    tlr = lr(t,c,B)
    ans = min(max(slr[0],tlr[0]),
              max(slr[1],tlr[1]),
              slr[0]*2+ tlr[1],
              slr[0]+ tlr[1]*2,
              slr[1]*2 + tlr[0],
              slr[1]+ tlr[0]*2
              )
    print(ans)
### BUGGY CODE ###

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

A=[]
answer=0
B=[]

for i in range(N):
    sum=0
    for j in range(1,p[i]+1):
        sum+=j
    A.append(sum/p[i])

for k in range(N-K+1):
    count=0
    for l in range(K):
        count+=A[k+l]
    B.append(count)

print(max(B))



### FIXED CODE ###

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

A=[]
base=0
B=[]

for i in range(N):
    if p[i]%2==0:
        A.append(((p[i]+1)*p[i]//2)/p[i])
    else:
        A.append((((p[i]+1)*(p[i]//2)+((p[i]+1)//2)))/p[i])
    
for l in range(K):
    base+=A[l]
B.append(base)
for k in range(K,N):
    base+=A[k]
    base-=A[k-K]
    B.append(base)    

print(max(B))
#print(A)
### BUGGY CODE ###

s=input()[::-1]
p=["maerd","remaerd","resare","esare"]
while True:
  if s[:5]==p[0]:s.replace(p[0],"",1)
  elif s[:5]==p[3]:s.replace(p[3],"",1)
  elif s[:7]==p[1]:s.replace(p[1],"",1)
  elif s[:6]==p[2]:s.replace(p[2],"",1)
  else:
    if s=="":print("YES");break
    else:print("NO");break

### FIXED CODE ###

s=input()[::-1]
p=["maerd","remaerd","resare","esare"]
while True:
  if s[:5]==p[0]:s=s[5:]
  elif s[:5]==p[3]:s=s[5:]
  elif s[:7]==p[1]:s=s[7:]
  elif s[:6]==p[2]:s=s[6:]
  else:
    if s=="":print("YES");break
    else:print("NO");break
### BUGGY CODE ###

#! /usr/bin/env python3

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

A, B, N = [int(_) for _ in input().split()]

def floor(t):
    return t // 1

ma = 0
x = 0
a_b = A/B

while True:
    if x > N: break
    a = floor(a_b*x) - A * floor(x/B)
    x += 1
    if a > ma:
        ma = a

print(int(ma))   

### FIXED CODE ###

#! /usr/bin/env python3

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

A, B, N = [int(_) for _ in input().split()]

x = min(B-1, N) # 0 <= x < B and 0 <= x <= N
a = (A * x) // B - A * (x // B)

print(int(a))
### BUGGY CODE ###

import queue
q = queue.Queue()
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
x=[[-1,0],[1,0],[0,-1],[0,1]]
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            a[i][j]=0
            for k in x:
                if 0<=i+k[0]<h and 0<=j+k[1]<w and a[i+k[0]][j+k[1]]==".":
                    a[i+k[0]][j+k[1]]=1
                    q.put([i+k[0],j+k[1],1])
ans=0
while not q.empty():
    v=q.get()
    for k in x:
        if 0<=v[0]+k[0]<h and 0<=v[1]+k[1]<w and a[v[0]+k[0]][v[1]+k[1]]==".":
            a[v[0]+k[0]][v[1]+k[1]]=v[2]+1
            q.put([v[0]+k[0],v[1]+k[1],v[2]+1])
            ans=v[2]+1
print(ans)

### FIXED CODE ###

from collections import deque 
import sys
input = sys.stdin.readline
def main():
    q = deque([])
    h,w=map(int,input().split())
    a=[list(input()) for i in range(h)]
    x=[[-1,0],[1,0],[0,-1],[0,1]]
    for i in range(h):
        for j in range(w):
            if a[i][j]=="#":
                for k in x:
                    if 0<=i+k[0]<h and 0<=j+k[1]<w and a[i+k[0]][j+k[1]]==".":
                        a[i+k[0]][j+k[1]]="0"
                        q.append([i+k[0],j+k[1],1])
    ans=0
    while q:
        v=q.popleft()
        for k in x:
            if 0<=v[0]+k[0]<h and 0<=v[1]+k[1]<w and a[v[0]+k[0]][v[1]+k[1]]==".":
                a[v[0]+k[0]][v[1]+k[1]]="0"
                q.append([v[0]+k[0],v[1]+k[1],v[2]+1])
                ans=v[2]+1
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

saidai = 0

for i in range (n):
    count = 0
    for j in range (n-i-1):
        if int(h[i+j])>=int(h[i+j+1]):
            count = count+1
        else :
            i = i + j
            break
    saidai = max(saidai,count)

print(saidai)


### FIXED CODE ###

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

for i in range (n-1):
    if h[i]>=h[i+1]:
        count += 1
    else:
        m = max(m,count)
        count = 0
m = max(m,count)
print(m)
### BUGGY CODE ###

mod = 10 ** 9 + 7
N = int(input())
A = [int(a) for a in input().split()]

# Nが偶数ならAiは全て奇数、Nが奇数なら Aiは全て偶数でなければならない,なぜなら、2x + Ai = N - 1を満たすxが自然数(非負整数)でなければならないから
# さらに、Nが奇数の時はfor i in range(0, N, 2) において 0が１個、それ以外のiが２個ずつ存在しなければならず(これはAiが全て偶数であることも満たしている)、
# Nが偶数の時はfor i in range(1, N, 2) において 全てのiが２個ずつ存在しなければならない(これはAiがすべて奇数であることも満たしている)
# これを踏まえた上でNが偶数の時は N/2人の位置が決まれば反対側の人の位置も決まり、Nが奇数の時は中央の人は固定として、それ以外 (N-1)/2人の位置が決まれば残りの人は反対側で位置が決まる。それぞれ２通りなので、
# よって
if N % 2 != 0:
    for i in range(0, N, 2):
        if A.count(i) == 2:
            continue
        elif A.count(0) == 1:
            continue
        print(0)
        exit()
    
    #order_count = 1
    #for i in range((N - 1) // 2):
    order_count = 2 ** ((N - 1) // 2) % mod

else:
    for i in range(1, N, 2):
        if A.count(i) != 2:
            print(0)
            exit()
    #order_count = 1
    #for i in range(N // 2):
    order_count = 2 ** (N // 2) % mod

print(order_count)




### FIXED CODE ###

mod = 10 ** 9 + 7
N = int(input())
A = [int(a) for a in input().split()]
A.sort()

if N % 2 != 0:
    if A[0] == 0:
        for i in range(2, N, 2):
            if not (A[i] == i and A[i-1] == i):
                print(0)
                exit()
        order_count = 2 ** ((N - 1) // 2) % mod
    else:
        print(0)
        exit()

else:
    for i in range(1, N, 2):
        if not (A[i] == i and A[i-1] == i):
            print(0)
            exit()
    order_count = 2 ** (N // 2) % mod 

print(order_count)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def inv(x):
    return pow(x, mod - 2, mod)

cms = 10**6 * 2 + 5
cm = [0] * cms

def comb_init():
    cm[0] = 1
    for i in range(1, cms):
        cm[i] = cm[i-1] * i % mod

def comb(a, b):
    return (cm[a] * inv(cm[a-b]) % mod) * inv(cm[b]) % mod

def main():
    r1,c1,r2,c2 = LI()
    comb_init()

    r = 0
    for i in range(r1+1, r2+2):
        r += comb(i+c2, c2)
        r -= comb(i+c1-1, c1-1)
        r %= mod

    return r

print(main())





### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def inv(x):
    return pow(x, mod - 2, mod)

def main():
    r1,c1,r2,c2 = LI()

    r = 0
    t1 = 1
    u1 = c2 + 1
    t2 = 1
    u2 = c1
    for i in range(1, r2+2):
        t1 *= u1
        t1 %= mod
        u1 += 1
        t1 *= inv(i)
        t1 %= mod
        t2 *= u2
        t2 %= mod
        u2 += 1
        t2 *= inv(i)
        t2 %= mod
        if i > r1:
            r += t1 - t2
            r %= mod

    return r

print(main())
### BUGGY CODE ###

N,K=map(int,input().split())
ans=0
for i in range(K,N+2):
    tmp=i*N-2*sum(range(0,i))+1
    ans+=tmp
    ans%=(10**9+7)
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
ans=0
for i in range(K,N+2):
    tmp=i*N-(i-1)*i+1
    ans+=tmp
    ans%=(10**9+7)
print(ans)