Harryxun/stf_run huggingface dataset:
from bisect import bisect_left

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

if X*Y*Z <= 1:
  D = sorted([A[i]+B[j]+C[k] for i in range(X) for j in range(Y) for k in range(Z)],reverse=True)
  for i in range(K):
    print(D[i])
  
else:
  A = sorted(A)
  D = sorted([B[i]+C[j] for i in range(Y) for j in range(Z)])

  thr = K
  s = A[-1]+D[max(0,len(D)-thr)]
  prev_idx=0
  selected = [A[-1] + D[i] for i in range(max(0,len(D)-thr),len(D))]
  
  for i in range(1,X):
    r = s - A[-1-i]
    if r<=0:break
    idx = bisect_left(D,r,prev_idx,len(D)-1)
    if idx == len(D):break
    selected.extend([A[-1-i] + D[j] for j in range(idx,len(D))])
    prec_idx = idx

  selected = sorted(selected,reverse=True)

  for i in range(K):
    print(selected[i])

### FIXED CODE ###

from bisect import bisect_left

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

if X*Y*Z <= 50000:
  D = sorted([A[i]+B[j]+C[k] for i in range(X) for j in range(Y) for k in range(Z)],reverse=True)
  for i in range(K):
    print(D[i])
  
else:
  A = sorted(A)
  D = sorted([B[i]+C[j] for i in range(Y) for j in range(Z)])

  thr = K
  s = A[-1]+D[max(0,len(D)-thr)]
  prev_idx=0
  selected = [A[-1] + D[i] for i in range(max(0,len(D)-thr),len(D))]
  
  for i in range(1,X):
    r = s - A[-1-i]
    if r<=0:break
    idx = bisect_left(D,r,prev_idx,len(D)-1)
    if idx == len(D):break
    selected.extend([A[-1-i] + D[j] for j in range(idx,len(D))])
    prec_idx = idx

  selected = sorted(selected,reverse=True)

  for i in range(K):
    print(selected[i])
n = int(input())

maxv =  int(-20000000)
minv = int(input())

for i in range(n):
    r= int(input())
    maxv = max(maxv, r-minv)
    minv = min(minv, r)

print(maxv)



### FIXED CODE ###

n = int(input())

maxv = -10**18
minv = 10**18

for i in range(n):
    r= int(input())
    maxv = max(maxv, r - minv)
    minv = min(minv, r)

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

CB = []
for _ in range(m):
    b, c = map(int, input().split())
    CB.append([c, b])

CB.sort(reverse=True)
A.sort()
index = 0
for i in range(m):
    if A[index] >= CB[i][0]:
        break

    for j in range(CB[i][1]):
        if A[index] >= CB[i][0]:
            break

        A[index] = CB[i][0]
        index += 1

print(sum(A))


### FIXED CODE ###

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

CB = []
for _ in range(m):
    b, c = map(int, input().split())
    CB.append([c, b])

CB.sort(reverse=True)
A.sort()
index = 0
for i in range(m):
    if index >= n:
        break
    elif A[index] >= CB[i][0]:
        break

    for j in range(CB[i][1]):
        if index >= n:
            break
        elif A[index] >= CB[i][0]:
            break

        A[index] = CB[i][0]
        index += 1

print(sum(A))
N = input()

if N==1:
	print ("Hello World")
elif N==2:
 	N1 = input()
	N2 = input()
	print (N1+N2)


### FIXED CODE ###

N = int(input())

if N==1:
 print ("Hello World")
elif N==2:
 N1 = int(input())
 N2 = int(input())
 print (N1+N2)
#C
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
i = 0
j = 0
while n > i or m > j:
    # print(i,j,k)
    if n <= i:
        k -= b[j]
        j += 1
        ans+=1
        continue
    elif n <= j:
        k -= a[i]
        i += 1
        ans+=1
        continue
    if a[i] < b[j]:
        k -= a[i]
        i += 1
    else:
        k -= b[j]
        j += 1
    if k < 0:
        break
    ans += 1
    if k == 0:
        break
print(ans)

### FIXED CODE ###

#C
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = [0]
B = [0]
#読書時間A,B
for i in range(n):
    A.append(A[i] + a[i])
for i in range(m):
    B.append(B[i] + b[i])
ans = 0
j = m
#Aを増やしたときA+Bがkより小さくなるようなi,jを決めて最大値を決めてる
for i in range(n + 1):
    if A[i] > k:
        break
    #K<=A[i]+B[j]となるまでjを引く>>k-A<=B
    while A[i] + B[j] > k:
        j -= 1
    ans = max(ans, i + j)
print(ans)
a, b = map(int, input())
if a >= 10 or b >= 10:
    print(int(a * b))

else:
    print(-1)


### FIXED CODE ###

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

if max(a, b) <= 9:
  print(a * b)
else:
  print(-1)
#!/mnt/c/Users/moiki/bash/env/bin/python
N, X = map(int, input().split())

def calcl(n):
    l = 2 ** (n+2) - 3 
    return l
def calcp(n):
    p = 2 ** (n+1) - 1
    return p
    
L = [1]
P = [1]

for i in range(1, N+1):
    L.append( L[i-1] * 2 + 3)
    P.append( P[i-1] * 2 + 1)

def judge(n, x):
    if x == 1:
        if n == 0:
            return "3"
        else:
            return "2"
    else:
        l = L[n]       # layers
        top = l-1
        bottom = 0
        mid = (l-1)//2 # index of middle

        if x == mid:
            return "3"
        elif top > x > mid:
            return "1"
        elif 0 < x < mid:
            return "0"            
        elif x == top:
            return "4"
        elif x == bottom:
            return "2"
        else:
            raise "No such pattern!"
        
    
def calc_pan(n,x, sum):
    c = judge(n,x)
    # print("calc_panK: n:{}, x:{}, c: {}".format(n,x,c))
    if  c == "2":
        return sum
    elif c == "4":
        return sum + 1 + P[n-1]
    elif c == "3":
        return sum + 1 
    elif c == "0":
        return sum + calc_pan(n-1, x-1, 0)
    elif c == "1":
        return sum + P[n-1] + 1 + calc_pan(n-1, x-L[n-1]-2, 0)





sum = calc_pan(N, X, 0)
print(sum)





### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N, X = map(int, input().split())

    
L = [1]
P = [1]

for i in range(0, N+1):
    L.append( L[i] * 2 + 3)
    P.append( P[i] * 2 + 1)

        
    
def calc_pan(n,x):
    # c = judge(n,x)
    if n == 0:
        return 0 if x <= 0 else 1
    elif x <= 1 + L[n-1]:
        return calc_pan(n-1, x-1)
    else:
        return P[n-1] + 1  + calc_pan(n-1, x - 2 - L[n-1])

sum = calc_pan(N, X)
print(sum)
import sys
A, B, K = map(int, input().split())
box = list(range(A, B+1))
if K >= 2*len(box):
    box.sort()
    for i in box:
        print(i)
    sys.exit()
box.sort()
temp1 = box[:K] + box[-K:]
temp = sorted(set(temp1), key=temp1.index)
temp.sort()
for i in temp:
    print(i)

### FIXED CODE ###

A, B, K = map(int, input().split())
L = [A+i for i in range(K) if A+i <= B]
R = [B-i for i in range(K) if B-i >= A]
S = set(L+R)
S = sorted(S)
for v in S:
    print(v)
n = int(input())
import sys

a = 'abcdefghij'
s = 'a'
count = 0

if n == 1:
  print('a')
  sys.exit()

for i in range(2):
  s.append(a[i])
  if i == 0:
    count += 1
  if count == n - 1:
    break
  for j in range(i + 1):
    s.append(a[i])
    if i == 0:
      count += 1
    if count == n - 1:
      break
    for k in range(j + 1):
      s.append(a[i])
      if i == 0:
        count += 1
      if count == n - 1:
        break
      for l in range(k + 1):
        s.append(a[i])
        if i == 0:
          count += 1
        if count == n - 1:
          break
        for m in range(l + 1):
          s.append(a[i])
          if i == 0:
            count += 1
          if count == n - 1:
            break
          for o in range(m + 1):
            s.append(a[i])
            if i == 0:
              count += 1
            if count == n - 1:
              break
            for p in range(o + 1):
              s.append(a[i])
              if i == 0:
                count += 1
              if count == n - 1:
                break
              for q in range(p + 1):
                s.append(a[i])
                if i == 0:
                  count += 1
                if count == n - 1:
                  break
print(s)
                
  

### FIXED CODE ###

n = int(input())

def dfs(s):
  if len(s) == n:
    print(s)
  else:
    for i in range(ord(max(s)) - ord('a') + 2):
      dfs(s + chr(i + ord('a')))
      
s = 'a'
dfs(s)
a, b = map(int, input().split())
if a%3==0 or b%3==0 or (a+b)%==0:
    print("Possible")
else:
    print("Impossible")

### FIXED CODE ###

a, b = map(int, input().split())
if a%3==0 or b%3==0 or (a+b)%3==0:
    print("Possible")
else:
    print("Impossible")
import sys
sys.setrecursionlimit(700000)
from math import factorial
N,K = map(int, input().split())
mod = 10**9 + 7
for i in range(1,K+1):
   
    comb = int(factorial(K-1) / factorial(i-1) / factorial(K-i) % mod)
   
    
    sec = int(factorial(N-K+1) / factorial(N-K-i+1) / factorial(i) % mod)
   
    print((comb * sec)%mod)

### FIXED CODE ###

from math import factorial
N,K = map(int, input().split())
mod = 10**9 + 7
def com(n,r):
    if n<r:
        return 0
    return int(factorial(n) // factorial(r) // factorial(n-r))
for i in range(1,K+1):
    comb = com(N-K+1,i)
    sec = com(K-1,i-1)
    print((comb * sec)%mod)
N = list(int(input()))

if N[0] == 9 or N[1] == 9:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

N = str(input())

if N[0] == "9" or N[1] == "9":
    print("Yes")
else:
    print("No")
ans = 0
for i in range(5):
  a = int(input())
  if a == 0:
    ans = i+1
print(ans)  


### FIXED CODE ###

a = list(map(int, input().split()))
for i in range(5):
  if a[i] == 0:
    print(i+1)
S = print()
T = print()
count == 0
#iを３回数えてもらう
for i in range(3)
#数えてｓとｔが同じならカウント１とする
if S[i] == T[i] 
    print(I)
count(I,num)

### FIXED CODE ###

S = input()
T = input()

count = 0
#iを３回数えてもらう
for i in range(3):
#数えてｓとｔが同じならカウント１とする
    if S[i]==T[i]:
        count += 1
print(count)
S, W = map(int, input().split())
if W>=S:
  print("unsafe")
 else:
  print("safe")

### FIXED CODE ###

S, W = map(int, input().split())
if W >= S:
    print("unsafe")
else:
    print("safe")
def main():
    n = input()
    

    if n%9==0:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    

    if n%9==0:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()
class Cmb:
    def __init__(self, N=10**5, mod=10**9+7):
        self.fact = [1,1]
        self.fact_inv = [1,1]
        self.inv = [0,1]
        
        """ 階乗を保存する配列を作成 """
        for i in range(2, N+1):
            self.fact.append((self.fact[-1]*i) % mod)
            self.inv.append((-self.inv[mod%i] * (mod//i))%mod)
            self.fact_inv.append((self.fact_inv[-1]*self.inv[i])%mod)
    
    """ 関数として使えるように、callで定義 """
    def __call__(self, n, r, mod=10**9+7):
        if (r<0) or (n<r):
            return 0
        r = min(r, n-r)
        return self.fact[n] * self.fact_inv[r] * self.fact_inv[n-r] % mod

n,a,b = map(int,input().split())
c = Cmb()
mod = 10**9+7
print((pow(2,n,mod) - 1 - c(n,a) - c(n,b))%mod)



### FIXED CODE ###

n,a,b = map(int,input().split())
mod = 10**9+7
ans = pow(2,n,mod)-1

comb1 = 1
for i in range(n-a+1, n+1):
    comb1 *= i
    comb1 %=  mod
for i in range(1, a+1):
    comb1 *= pow(i, mod-2, mod)
    comb1 %=  mod

comb2 = 1
for i in range(n-b+1, n+1):
    comb2 *= i
    comb2 %=  mod
for i in range(1, b+1):
    comb2 *= pow(i, mod-2, mod)
    comb2 %=  mod
ans -= (comb1 + comb2)
print(ans % mod)
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def lcm_base(a, b):
    return (a * b) // gcd(a, b)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def main():
    n, m = map(int, readline().split())
    a = np.array(input().split(), np.int64)
    a //= 2
    b = np.copy(a)
    while True:
        c = b % 2
        if c.sum() == 0:
            b //= 2
        elif c.sum() == n:
            break
        else:
            print(0)
            sys.exit()
    d = lcm_list(a)
    if d > 10 ** 9:
        ans = 0
    else:
        ans = (m // d) - (m // (d + d))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def main():
  n, m = map(int, readline().split())
  a = np.array(input().split(), np.int64)
  a //= 2
  b=np.copy(a)
  while True:
    c = b%2
    if c.sum() == 0:
      b //= 2
    elif c.sum() == n:
      break
    else:
      print(0)
      sys.exit()
  d = lcm_list(a)
  if d>10**9:
    ans = 0
  else:
    ans = (m//d) - (m//(d+d))
  print(ans)
  
  
  
if __name__ == '__main__':
  main()
# ABC 129, c
n, m = map(int, input().split())
dp = [int(el) for el in input().split(' ')]
dp[0] = 1
dp[1] = 1
for j in [int(input()) for j in range(m)]:
    dp[j] = -1
for i in range(n + 1):
    if i < 2:
        if dp[i] == -1:
            dp[i] = 0
    else:
        if dp[i] == -1:
            dp[i] = 0
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
print(dp[n])


### FIXED CODE ###

# ABC 129, c
n, m = map(int, input().split())
dp = [0 for i in range(n+1)]
dp[0] = 1
dp[1] = 1
for j in [int(input()) for j in range(m)]:
    dp[j] = -1
for i in range(n + 1):
    if i < 2:
        if dp[i] == -1:
            dp[i] = 0
    else:
        if dp[i] == -1:
            dp[i] = 0
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
print(dp[n])
n=int(input())
l=list(map(int,input().split()))
la=list(map(int,input().split()))

flag=0
for m,i in enumerate(la):
  ans+=min(i,l[m])+l[m+1]-max(0,l[m+1]-i+min(i,l[m]))
  l[m+1]=max(0,l[m+1]-i+min(i,l[m]))
print(ans)


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
la=list(map(int,input().split()))

ans=0
for m,i in enumerate(la):
  ans+=min(i,l[m])+l[m+1]-max(0,l[m+1]-i+min(i,l[m]))
  l[m+1]=max(0,l[m+1]-i+min(i,l[m]))
print(ans)
n,k = map(int, input().split())
s = input()

if n == 1:
  print(0)
  exit()

pre = s[0]
cont = 1
for c in s[1:]:
  if c != pre:
    if c == s[0]:
      two += 1
    ans += cont-1
    cont = 1
    pre = c
  else:
    cont += 1
ans += cont-1

if s[0] != s[1]:
  ans += 1
print(ans + 2*min(k,two))

### FIXED CODE ###

n, k = map(int, input().split())
s = input()

if n == 1:
    print(0)
    exit()

two = 0
pre = s[0]
cont = 1
ans = 0
for c in s[1:]:
    if c != pre:
        if c == s[0]:
            two += 1
        ans += cont - 1
        cont = 1
        pre = c
    else:
        cont += 1
ans += cont - 1

if s[0] != s[-1] and k > two:
    ans += 1
print(ans + 2 * min(k, two))
X = int(input())
base = 100
rt = 0
while X > base:
    base = math.floor(base * 1.01)
    rt += 1
print(rt)

### FIXED CODE ###

import math
X = int(input())
base = 100
rt = 0
while X > base:
    base = math.floor(base * 1.01)
    rt += 1
print(rt)
from collections import defaultdict
import random
INF = float('inf')
N, M = map(int, input().strip().split())
LRD = [list(map(int, input().strip().split())) for _ in range(M)]

LRD.sort(key=lambda x:min(x[0], x[1]))

dic = defaultdict(lambda: INF)
for i in range(M):
	if dic[LRD[i][0]] == INF and dic[LRD[i][1]] == INF:
		dic[LRD[i][0]] = random.randint()
		dic[LRD[i][1]] = dic[LRD[i][0]] + LRD[i][2]
	elif dic[LRD[i][0]] == INF and dic[LRD[i][1]] != INF:
		dic[LRD[i][0]] = dic[LRD[i][1]] - LRD[i][2]
	elif dic[LRD[i][0]] != INF and dic[LRD[i][1]] == INF:
		dic[LRD[i][1]] = dic[LRD[i][0]] + LRD[i][2]
	else:
		if dic[LRD[i][0]] + LRD[i][2] == dic[LRD[i][1]]:
			continue
		else:
			print("No")
			break
else:
	print("Yes")
  

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

graph = defaultdict(list)
for _ in range(M):
	L, R, D = MAP()
	graph[L-1].append((R-1, D))
	graph[R-1].append((L-1, -D))

num = [None]*N

for i in range(N):
	if num[i] != None:
		continue
	q = deque([i])
	num[i] = 0
	while q:
		n = q.popleft()
		for node, weight in graph[n]:
			if num[node] == None:
				num[node] = num[n] + weight
				q.append(node)
			else:  # 閉路⇒条件チェック
				if num[node]-num[n] != weight:
					print("No")
					exit()

print("Yes")
import sys


def input(): return sys.stdin.readline().strip()


N, M = (list)(map(int, input().split()))
edge = []

for _ in range(M):
    edge.append((list)(map(int, input().split())))


inf = 10**15

d = [inf]*(N+1)
d[1] = 0
ans = inf
for i in range(N):
    update = False
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d
            update = True

    if not update:
        break

neg = [False]*(N+1)
for i in range(N):
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d
            neg[b] = True
        if neg[a]:
            neg[b] = True

if neg[-1]:
    print('inf')
else:
    print(-d[-1])


### FIXED CODE ###

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

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

nums = sorted(nums, key=lambda x: x[0])

acc = [0]*N
acc[0] = nums[0][1]
for i in range(1, N):
    acc[i] += acc[i-1]+nums[i][1]


for i in range(N):
    if acc[i] >= K:
        print(nums[i][0])
        exit()
N = int(input())
A = list(map(int, input().split()))
# 全体の長さから右から数えて最初に出た1の箇所のインデックスを引く
# 後ろに続く0の数が2で割れる回数にあたる
# 例　全：6 インデックス 2 -1 
ans = float("inf")
for i in A:
    ans = min(ans, len(bin(i)) - bin(i).rfind("1") -1 )
print(ans)

### FIXED CODE ###

s = input()
print(s.count('1'))
n = input()
li = []
for i in n:
  li.append(int(i))
if n % sum(li) == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n = input()
li = []
for i in n:
  li.append(int(i))
if int(n) % sum(li) == 0:
  print("Yes")
else:
  print("No")
A = [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]
K = int(input())
print(A[K+1])

### FIXED CODE ###

lists = [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]
k = int(input())
print(int(lists[k-1]))
N = int(input())
nums = input().split(" ")
nums2 = [int(x)-i-1 for i,x in enumerate(nums)]
nums2.sort()
length = len(nums2)
numpre = 0
same = 1
for n,m in zip(nums2[:-1],nums2[1:]):
  if n == m:
    same += 1
  else:
    impact = same + numpre
    if impact > length-impact:
      value = n
      break
    numpre += same
    same = 1
  value = m

answer = 0
for i in nums2:
  answer += abs(i-value)
print(answer)

### FIXED CODE ###

N = int(input())
nums = input().split(" ")
nums2 = [int(x)-i-1 for i,x in enumerate(nums)]
nums2.sort()
length = len(nums2)
numpre = 0
same = 1
if length == 1:
  value = nums2[0]
 
for n,m in zip(nums2[:-1],nums2[1:]):
  if n == m:
    same += 1
  else:
    impact = same + numpre
    if impact > length-impact:
      value = n
      break
    numpre += same
    same = 1
  value = m
 
answer = 0
for i in nums2:
  answer += abs(i-value)
print(answer)
mod = 10 ** 9 + 7
N = 2 * 10 ** 6

fac = [0] * N
finv = [0] * N
inv = [0] * N

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, N):
    fac[i] = fac[i - 1] * i % mod
    # mod pにおける1, 2, ..., nの逆元
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def com(n, k):
    global fac, finv, mod
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


r1, c1, r2, c2 = map(int, input().split())
answer = 0

for r in range(r1, r2 + 1):
    for c in range(c1, c2 + 1):
        answer += com(r + c, c)
        answer %= mod
print(answer)


### FIXED CODE ###

mod = 10 ** 9 + 7
N = 2 * 10 ** 6 + 10

fac = [0] * N
finv = [0] * N
inv = [0] * N

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, N):
    fac[i] = fac[i - 1] * i % mod
    # mod pにおける1, 2, ..., nの逆元
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def com(n, k):
    global fac, finv, mod
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod

def g(r, c):
    return (com(r + c + 2, r + 1) - 1) % mod

r1, c1, r2, c2 = map(int, input().split())

answer = g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)
answer %= mod
print(answer)
N, M = map(int, input().split())
a = []
tmp = []
for i in range(M):
    tmp = list(map(str,input().split()))
    a.append(list(tmp[0]))


cpi = [-1,0,0,1]
cpj = [0,-1,1,0]

smFlag = False
result = True

for i in range(N):
    for j in range(M):
        if a[i][j] == '#':
            for x,y in zip(cpi,cpj):
                if i + x > -1 and j + y > -1 and i + x < N  and j + y < M:
                    if a[i+x][j+y] == '#':
                        smFlag = True
            if not smFlag:
                print('No')
                result = False

if result:
    print('Yes')


### FIXED CODE ###

H, W = map(int, input().split())
a = []
tmp = []
for i in range(H):
    tmp = list(map(str,input().split()))
    a.append(list(tmp[0]))

for i in range(H):
    for j in range(W):
        if a[i][j] == '#':
            if j - 1 >= 0 and a[i][j - 1] == "#":
                continue
            elif j + 1 < W and a[i][j + 1] == "#" :
                continue
            elif i + 1 < H and a[i + 1][j] == "#" :
                continue
            elif i - 1 >= 0 and a[i - 1][j] == "#":
                continue
            else:
                print("No")
                exit()
 
print("Yes")
A = int(A)
B = int(B)
T = int(T)

count = (T + 0.5) // A
biscuit = B * count
print(biscuit)


### FIXED CODE ###

A, B, T = map(int, input().split())

count = T // A
bsc = B * count

print(bsc)