Harryxun/stf_run huggingface dataset:
import sys

read= sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 1000000007
sys.setrecursionlimit(10**7)

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



#増減のメモ 
# A[i] > A[i+1]  :  1
# A[i] < A[i+1]  : -1
# A[i] == A[i+1] :  0
x = []
for i in range(N-1):
    if A[i]  < A[i+1]:
        x.append(1)
    elif A[i] > A[i+1]:
        x.append(-1)
    else:
        x.append(0)


res = 1  #答え

#print(len(x))
state = x[0] #単調増加 or 単調減少の二種で現在の状態を記録
i = 1
while  i < N-1:
    if x[i] ==  state or state == 0:
        pass
    else:
        if i != N -2:
            state = x[i+1]
            i+=1
            res+=1
    i+=1

if x[-1] != x[-2] and x[-1] != 0 and x[-2]!= 0 :
    print(res+1)
else:
    print(res)


### FIXED CODE ###

import sys

read= sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 1000000007
sys.setrecursionlimit(10**7)

#N,*A = map(int,read().split())
N = int(input())
l = list(map(int,input().split()))

#最初の状態分を加算するため、1からカウント
ans = 1

S = 0 #現在の状態 増加 or 減少 or 初期化

for i in range(1,N):
    X = l[i] - l[i-1]

    X = 0 if X == 0 else 1 if X > 0 else -1

    #同じ値の時l[i] == l[i-1]
    if X == 0:
        continue

    #Stateが初期のときは現在の状態に更新
    elif S == 0:
        S = X

    #Stateが違うときは答えに加算して、Stateを初期値に
    elif S != X:
        ans += 1
        S = 0

print(ans)
N=int(input())
P=[int(N) for N in input().split()]

a=-100
for i in range(N):
  if a<P[i]:
    a=P[i]

P.remove(a)

goukei=a/2
for j in range(N-1):
  goukei+=P[j]

print(int(goukei))

### FIXED CODE ###

D=int(input())
if D==25:
  print("Christmas")
elif D==24:
  print("Christmas Eve")
elif D==23:
  print("Christmas Eve Eve")
elif D==22:
  print("Christmas Eve Eve Eve")
a, b, c, d = list(input())
a, b, c, d = int(a), int(b), int(c), int(d)
if a+b+c+d == 7:
  print(str(a)+'+'+str(b)+'+'+str(c)+'+'+str(d)+'=7')
elif a+b+c-d == 7:
  print(str(a)+'+'+str(b)+'+'+str(c)+'+'+str(d)+'=7')
elif a+b-c+d == 7:
  print(str(a)+'+'+str(b)+'-'+str(c)+'+'+str(d)+'=7')
elif a+b-c-d == 7:
  print(str(a)+'+'+str(b)+'-'+str(c)+'+'-str(d)+'=7')
elif a-b+c+d == 7:
  print(str(a)+'-'+str(b)+'+'+str(c)+'+'+str(d)+'=7')
elif a-b+c-d == 7:
  print(str(a)+'-'+str(b)+'+'+str(c)+'+'-str(d)+'=7')
elif a-b-c+d == 7:
  print(str(a)+'-'+str(b)+'-'+str(c)+'+'+str(d)+'=7')
elif a-b-c-d == 7:
  print(str(a)+'-'+str(b)+'-'+str(c)+'+'-str(d)+'=7')


### FIXED CODE ###

s = input()
a, b, c, d = int(s[0]), int(s[1]), int(s[2]), int(s[3])
if a+b+c+d == 7:
  print(str(a)+'+'+str(b)+'+'+str(c)+'+'+str(d)+'=7')
elif a+b+c-d == 7:
  print(str(a)+'+'+str(b)+'+'+str(c)+'-'+str(d)+'=7')
elif a+b-c+d == 7:
  print(str(a)+'+'+str(b)+'-'+str(c)+'+'+str(d)+'=7')
elif a+b-c-d == 7:
  print(str(a)+'+'+str(b)+'-'+str(c)+'-'+str(d)+'=7')
elif a-b+c+d == 7:
  print(str(a)+'-'+str(b)+'+'+str(c)+'+'+str(d)+'=7')
elif a-b+c-d == 7:
  print(str(a)+'-'+str(b)+'+'+str(c)+'-'+str(d)+'=7')
elif a-b-c+d == 7:
  print(str(a)+'-'+str(b)+'-'+str(c)+'+'+str(d)+'=7')
elif a-b-c-d == 7:
  print(str(a)+'-'+str(b)+'-'+str(c)+'-'+str(d)+'=7')
n = int(input())
box  = []
prime = []
ans = 0
def Prime_Factorization(n):
    i = 2
    prime_factors = []
    while n > 1:
        if n % i == 0:
            prime_factors.append(i)
            n = n / i
        else:
            i += 1
    return prime_factors

for i in range(1,n):
    prime = Prime_Factorization(i)
    box.append(prime.count(2))
    #print(box)

ans = box.index(max(box)) + 1
print(ans)


### FIXED CODE ###

n = int(input())
box  = []
prime = []
ans = 0
def Prime_Factorization(n):
    i = 2
    prime_factors = []
    while n > 1:
        if n % i == 0:
            prime_factors.append(i)
            n = n / i
        else:
            i += 1
    return prime_factors

for i in range(1,n+1):
    prime = Prime_Factorization(i)
    box.append(prime.count(2))
    #print(box)


if n == 1:
    print(1)
else:
    ans = box.index(max(box)) + 1
    print(ans)
N, M = map(int, input().split())
s = []
c = []
num = ""

def judge():
    for i in range(M):
        s1, c1 = map(int, input().split())
        s.append(s1)
        c.append(c1)

    for i in range(M):
        for j in range(M):
            if s[i] == s[j] and i != j and c[i] != c[j]:
                print(-1)
                return

    if N == 3:        
        for i in range(M):
            if s[i] - 1 < 0 or s[i] - 1 > 2:
                print(-1)
                return
    elif N == 2:
        for i in range(M):
            if s[i] - 1 < 0 or s[i] - 1 > 1:
                print(-1)
                return
    else:
        if s[i] != 1:
                print(-1)
                return

    for i in range(M):
        num[s[i] - 1] = c[i]


    if num[0] == 0:
        if num[1] == 0:
            if num[2] == 0:
                print(-1)
                return
            print(num[2])
        print("{0}{1}".format(num[1], num[2]))
        return
    else:
        print("{0}{1}{2}".format(num[0], num[1], num[2]))
        return

judge()


### FIXED CODE ###

N, M = map(int, input().split())
sc = []
for i in range(M):
    sp, cp = map(int, input().split())
    sc.append((sp, cp))

ans = 10000

if N == 1:
    for i in range(10):
        num = str(i)
        flag = True
        for pair in sc:
            if (num[pair[0] - 1] != str(pair[1])):
                flag = False
                break
        if flag:
            ans = min(ans, i)
else:
    for i in range(10 ** (N - 1), 10 ** N):
        num = str(i)
        flag = True
        for pair in sc:
            if (num[pair[0] - 1] != str(pair[1])) or len(num) < pair[0]:
                flag = False
                break
        if flag:
            ans = min(ans, i)

if ans == 10000:
    ans = -1
print(ans)
k = int(input())
x = 7
ans = 1
if k%2 == 0 or k%5 ==0:
  ans = -1
elif 7%k == 0:
  ans = 1
else:
  for i in range(k)
    ans +=1
    x = x*10+7
    if x%k == 0:
      break


print(ans)



### FIXED CODE ###

k = int(input())
x = 7
ans = 1
if k%2 == 0 or k%5 ==0:
  print(-1)
  exit()
elif 7%k == 0:
  ans = 1

else:
  for i in range (1,k):
    x = (x*10+7)%k

    if x%k == 0:
      ans = i+1
      break

print(ans)
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

dp = [-1 for _ in range(n)]

def checker(s, g):
    if s > g:
        return 0
    elif s == g:
        return 1
    else:
        if dp[g - s] != -1:
            return dp[g - s]
        else:
            ret = checker(s + 1, g) + checker(s + 2, g)
            dp[g - s] = ret
            return ret

s = 0
g = a[0] - 1
if g - s > 0:
    c = checker(s, g)
else:
    c = 1
for i in range(1, m):
    if a[i - 1] + 1 == a[i]:
        c = 0
        break
    else:
        s = a[i - 1] + 1
        g = a[i] - 1
        if g - s > 0:
            c *= checker(s, g)
        s = a[m - 1] + 1
        g = n
if g - s > 0:
    c *= checker(s, g)

print(c % 1000000007)


### FIXED CODE ###

n, m = map(int, input().split())
a = [True for _ in range(n + 1)]
for _ in range(m):
    a[int(input())] = False

dp = [0] * (n + 1)
dp[0] = 1

for now in range(n):
    for next in range(now + 1, min(n + 1, now + 3)):
        if a[next]:
            dp[next] += dp[now]
            dp[next] %= 1000000007

print(dp[n])
import math
 
prime = [0 for i in range(11000
k = 0
r = 105000
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        prime[k] = i+1
        k += 1
        l = i
        for j in range(2*i+1,r,i+1):
            p[j] = 0


for i in range(l,r):
    if p[i]:
        prime[k] = i+1
        k += 1
        
while True:
    n = int(raw_input())
    if not n:
        break
    print sum(prime[:n])

### FIXED CODE ###

import math

r = 105000
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

s = [0 for i in range(11000)]
s[0] = 2
k = 1
for i in range(2,r):
    if p[i]:
        s[k] = i+1+s[k-1]
        k += 1
        
while True:
    n = int(raw_input())
    if not n:
        break
    print s[n-1]
N ,K =(int(x) for x in input().split(' '))

s = 0

for a in range(K,N+2) :
  
  SUM1 = sum([x for x in range(0,a)])
  SUM2 = sum([x for x in range(N-a+1, N+1)])
  
  s = s + SUM2 - SUM1 + 1
  
print(s%10**9+7)

### FIXED CODE ###

import math
a = input()
b = math.pi
print(2*int(a)*b)
inport sys
for i in sys.stdin.readlines():
        a,b = i.strip().split()
        if x == "0" and y == "0":
                break;

        if int(x) < int(y):
                print("{} {}".format(x,y))
        else:
                print("{} {}".format(y,x))
        

### FIXED CODE ###

import sys
for i in sys.stdin.readlines():
        a,b = i.strip().split()
        if a == "0" and b == "0":
                break

        if int(a) < int(b):
                print("{0} {1}".format(a,b))
        else:
                print("{1} {0}".format(a,b))
import sys
for e in sys.stdin:print(float(e)**(1/3))


####################################################
####################################################
####################################################
####################################################
####################################################
####################################################
####################################################
####################################################
####################################################
####################################################
########################################################################################################
####################################################
####################################################
########################################################################################################v
############################################################################################################################################################
####################################################
####################################################
####################################################
########################################################################################################v
vv####################################################


### FIXED CODE ###

for e in iter(input,'-1'):
 q=float(e)
 x=q/2
 while abs(x**3-q)>=q*1e-5:x-=(x**3-q)/3/x/x
 print(x)
a = list(map(int, input().split())).sort()
print(a[-1] * 10 + a[0] + a[1])

### FIXED CODE ###

a = sorted(map(int, input().split()))
print(a[-1] * 10 + a[0] + a[1])
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
def list_dif(l1, l2):
    result = l1.copy()
    for v in l2:
        if v in result:
            result.remove(v)
    return result
H = defaultdict(lambda: [])
N = int(input())
A = sorted(inpl())
ans = 0
for j in range(29,0,-1):
    k = 2**j
    t = []
    H = defaultdict(lambda: [])
    for i in A:
        if k <= i:
            break
        if H[k-i]:
            t.append(H[k-i].pop())
            t.append(i)
            ans += 1
        else:
            H[i].append(i)
    A = list_dif(A, t)
print(ans)

### FIXED CODE ###

import bisect
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
H = defaultdict(lambda: [])
Ad = defaultdict(lambda: 0)
N = int(input())
A = inpl()
for i in A:
    Ad[i] += 1
A = list(set(A))
A.sort()
ans = 0
for j in range(30,0,-1):
    k = 2**j
    H = defaultdict(lambda: [])
    ml = bisect.bisect_left(A, k) 
    for i in A[:ml]:
        if 2*i == k:
            ans += Ad[i]//2
            del Ad[i]
            continue
        if H[k-i]:
            m = min(Ad[k-i], Ad[i])
            Ad[k-i] -= m
            del Ad[i]
            ans += m
        else:
            H[i] = j
print(ans)
import math
import sys
inp = input()
N,A,B,K = list(map(int,inp.split()))
g = math.gcd(A,B)
if K % g != 0:
    print(0)
    sys.exit()
A = A // g
B = B // g
K = K // g
xn = []
yn = []
for i in range(10 ** 100):
    if (A * i- K) % B == 0:
        n = i
        xn.append(n)
        yn.append((K - A *n) // B)
        break
if yn[-1] < 0:
    if K % B == 0 and (K // B <= N):
        print(1)
    else:
        print(0)
    sys.exit()
while True:
    x  = xn[-1] + B
    y  = yn[-1] - A
    if y < 0:
        break
    xn.append(x)
    yn.append(y)
ans = 0
P = 998244353
def inv(n):
  return pow(n, P-2, P)
fact = [1] * (N+1)
for i in range(1, N+1):
  fact[i] = fact[i-1] * i % P
invfact = [inv(fact[N])] * (N+1)
for i in range(N, 0, -1):
  invfact[i-1] = invfact[i] * i % P
def comb(n, k):
  return fact[n] * invfact[k] * invfact[n-k] % P 
 
for x,y in zip(xn,yn):
    if N-x< 0 or N -y < 0:
        continue 
    ans = (ans + (comb(N,x) * comb(N,y)) % P)
print(ans)

### FIXED CODE ###

import math
import sys
import fractions
inp = input()
N,A,B,K = list(map(int,inp.split()))
# g = math.gcd(A,B)
g = fractions.gcd(A,B)
if K % g != 0:
    print(0)
    sys.exit()
A = A // g
B = B // g
K = K // g
xn = []
yn = []
for i in range(10 ** 100):
    if (A * i- K) % B == 0:
        n = i
        xn.append(n)
        yn.append((K - A *n) // B)
        break
if yn[-1] < 0:
    if K % B == 0 and (K // B <= N):
        print(1)
    else:
        print(0)
    sys.exit()
while True:
    x  = xn[-1] + B
    y  = yn[-1] - A
    if y < 0:
        break
    xn.append(x)
    yn.append(y)
ans = 0
P = 998244353
def inv(n):
  return pow(n, P-2, P)
fact = [1] * (N+1)
for i in range(1, N+1):
  fact[i] = fact[i-1] * i % P
invfact = [inv(fact[N])] * (N+1)
for i in range(N, 0, -1):
  invfact[i-1] = invfact[i] * i % P
def comb(n, k):
  return fact[n] * invfact[k] * invfact[n-k] % P 
 
for x,y in zip(xn,yn):
    if N-x< 0 or N -y < 0:
        continue 
    ans = (ans + (comb(N,x) * comb(N,y))) % P
print(ans)
n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n-1)]
px = [list(map(int, input().split())) for _ in range(q)]

cnt = [0 for _ in range(n)]
for p, x in px:
    cnt[p-1] += x

edge = [[] for _ in range(n)]
for a, b in ab:
    edge[a-1].append(b)
    edge[b-1].append(a)


def dfs(now, bef):
    for nxt in edge[now-1]:
        if nxt != bef:
            cnt[nxt-1] += cnt[now-1]
            dfs(nxt, now)


dfs(1, 0)
print(*cnt[1:])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)


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


N, Q = map(int, input().split())
ab = [[] for _ in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  ab[a-1].append(b)
  ab[b-1].append(a)

P = [0 for _ in range(N)]
for i in range(Q):
  p, x = map(int, input().split())
  P[p-1] += x


def dfs(p, par):
  for i in ab[p-1]:
    if i != par:
      P[i-1] += P[p-1]
      dfs(i, p)


dfs(1, -12345)
print(" ".join(map(str, P)))
#4
N = int(input())
x,y,k = 0,0,0

x = int(0.8*N)

for i in range(x,N):
    k = str(int(i*108))
    if int(k[0:-2]) == N:
        print(i)
        y +=1
        break

if y !=1:
    print(":(")


### FIXED CODE ###

#4
import sys
N = int(input())
x,y,k = 0,0,0

if N == 1:
    print(1)
    sys.exit()
elif N <= 12:
    print(N)
    sys.exit()
x = int(0.8*N)

for i in range(x,N):
    k = str(i*108)
    if int(k[0:-2]) == N:
        print(i)
        y +=1
        break

if y !=1:
    print(":(")
while 1:
    try:
        a,b = int(input().split())
        c = a + b
        print(len(str(c)))
    except EOFError:
        break


### FIXED CODE ###

while 1:
    try:
        a,b = input().split()
        a = int(a)
        b = int(b)
        c = a + b
        print(len(str(c)))
    except EOFError:
        break
import math


def solve():
    a, b, c, d = map(int, input().split())
    lcm = c * d // math.gcd(c, d)
    num_b = b - b // c - b // d + b // lcm
    a -= 1
    num_a = a - a // c - a // d + a // lcm
    return num_b - num_a


if __name__ == "__main__":
    print(solve())


### FIXED CODE ###

import fractions


def solve():
    a, b, c, d = map(int, input().split())
    lcm = c * d // fractions.gcd(c, d)
    div_c = b // c - (a - 1) // c
    div_d = b // d - (a - 1) // d
    div_cd = b // lcm - (a - 1) // lcm
    return (b - a + 1) - div_c - div_d + div_cd


if __name__ == "__main__":
    print(solve())
#!/usr/bin/env python3
import sys
import heapq
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    heapq.heapify(A)

    for b, c in zip(B, C):
        for i in range(b):
            v = heapq.heappop(A)
            if v < c:
                heapq.heappush(A, c)
            else:
                heapq.heappush(A, v)
                break
    return sum(A)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    result = solve(N, M, A, B, C)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
import heapq
import bisect
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    ret = sum(A)
    cs = Counter(A)
    for c in C:
        if c not in cs:
            cs[c] = 0
    vs = sorted(cs.keys())

    i = 0
    while cs[vs[i]] == 0:
        i += 1

    for b, c in zip(B, C):
        while 0 < b:
            if c <= vs[i]:
                break
            bb = min(b, cs[vs[i]])
            b -= bb
            cs[vs[i]] -= bb
            cs[c] += bb
            ret += bb * (c - vs[i])
            if cs[vs[i]] == 0:
                i += 1
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]" 
    C = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    result = solve(N, M, A, B, C)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()
A,B,K = map(int,input().split())
ans = []
for i in range(A,A+K):
    if i <= B:
        ans.append(i)
for i in range(B-K+1,B+1):
    if not i in ans and A <= i:
        ans.append(i)
for i in ans:


### FIXED CODE ###

A,B,K = map(int,input().split())
ans = []
for i in range(A,A+K):
    if i <= B:
        ans.append(i)
for i in range(B-K+1,B+1):
    if not i in ans and A <= i:
        ans.append(i)
for i in ans:
    print(i)
from operator import mul
from functools import reduce

def cmb(n, r):
    r = min(n - r, r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

a = cmb(n, r)
N, K = map(int, input().split())
for i in range(K):
    # a = factorial(N-K+1) / factorial(i+1) / factorial(N-K+1 - (i+1))
    a = cmb(N-K+1, i + 1)
    # b = factorial(K-1) / factorial(i) / factorial(K-1 - i)
    b = cmb(K-1, i)

    print((a*b) % (10**9+7))

### FIXED CODE ###

from operator import mul
from functools import reduce

def cmb(n, r):
    r = min(n - r, r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under % (10 ** 9 + 7)

N, K = map(int, input().split())
for i in range(K):
    if N-K+1 >= i + 1 and K-1 >= i:
        # a = factorial(N-K+1) / factorial(i+1) / factorial(N-K+1 - (i+1))
        a = cmb(N-K+1, i + 1)
        # b = factorial(K-1) / factorial(i) / factorial(K-1 - i)
        b = cmb(K-1, i)
        print((a*b) % (10**9+7))
    else:
        print(0)
r1, c1, r2, c2 = map(int, input().split())
N = 10 ** 6 + 1000
MOD = 10 ** 9 + 7
def createFacArr(n, mod):
    '''
    二項係数計算用の配列の作成

    Parameters
    n : int
        配列のサイズ
    mod : int
        あまり

    Returns
    fac : list
        階乗のリスト
    finv : list
        modの逆元のリスト
    ivn : list
    '''
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, n):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
    return fac, finv
fac, finv = createFacArr(N+100, MOD)

def comb(n ,k, mod):
    '''
    二項係数の計算

    Parameters
    n : int
        元集合
    k : int
        元集合から選択する数
    mod : int
        あまり
    fac : list
        階乗のリスト
    finv : list
        逆元のリスト
    
    Returns
    c : int
        nCkの組み合わせの数
    '''
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = 0

for c in range(c1,c2+1):
    ans += comb(r2+c+1, c+1, MOD) - comb(r1-1+c+1, c+1, MOD)
    ans %= MOD

print(ans)



### FIXED CODE ###

def createFacArr(n, mod):
    '''
    二項係数計算用の配列の作成

    Parameters
    n : int
        配列のサイズ
    mod : int
        あまり

    Returns
    fac : list
        階乗のリスト
    finv : list
        modの逆元のリスト
    ivn : list
    '''
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, n):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
    return fac, finv

def comb(n ,k, mod, fac, finv):
    '''
    二項係数の計算

    Parameters
    n : int
        元集合
    k : int
        元集合から選択する数
    mod : int
        あまり
    fac : list
        階乗のリスト
    finv : list
        逆元のリスト
    
    Returns
    c : int
        nCkの組み合わせの数
    '''
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod
MOD = 10 ** 9 + 7
fac, finv =  createFacArr(10**7, MOD)

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

ans = 0
for r in range(r1,r2+1):
    ans += comb(r+c2+1,c2, MOD, fac, finv)-comb(r+c1, c1-1,MOD, fac, finv)
    ans %= MOD
print(ans)