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

import collections

n, q = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(n - 1)]
counter = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    counter[p - 1] += x

tree = [[] for _ in range(n)]
edge = collections.deque(edge)
flag = [False] * n
flag[0] = True
while len(edge) != 0:
    a, b = edge.popleft()
    if flag[a - 1]:
        tree[a - 1].append(b - 1)
        flag[b - 1] = True
    elif flag[b - 1]:
        tree[b - 1].append(a - 1)
        flag[a - 1] = True
    else:
        edge.append((a, b))

que = collections.deque([0])
while len(que) != 0:
    i = que.popleft()
    for j in tree[i]:
        counter[j] += counter[i]
        que.append(j)

print(' '.join([str(c) for c in counter]))

### FIXED CODE ###

import collections

n, q = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(n - 1)]
counter = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    counter[p - 1] += x

tree = [[] for _ in range(n)]
edge = collections.deque(edge)
while len(edge) != 0:
    a, b = edge.popleft()
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)

que = collections.deque([0])
flag = [False] * n
while len(que) != 0:
    i = que.popleft()
    flag[i] = True
    for j in tree[i]:
        if flag[j]: continue
        counter[j] += counter[i]
        que.append(j)

print(' '.join([str(c) for c in counter]))
### BUGGY CODE ###

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort()
X = [XH[i][0] for i in range(N)]
ans = 0
res = 0
from bisect import bisect_left
cnt = [0]*(N+1)
for i in range(N):
    x, h = XH[i]
    res-=cnt[i]
    h-=res
    if h<=0:
        continue
    n = ((h-1)//A+1)
    j = bisect_left(XH, [x+D*2+1, -1])
    cnt[j] += n*A
    res += n*A
    ans+=n
print(ans)
    





### FIXED CODE ###


N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort()
X = [XH[i][0] for i in range(N)]
ans = 0
res = 0
from bisect import bisect_left
cnt = [0]*(N+1)
for i in range(N):
    x, h = XH[i]
    res-=cnt[i]
    h-=res
    if h<=0:
        continue
    n = ((h-1)//A+1)
    j = bisect_left(X, x+D*2+1)
    cnt[j]+=n*A
    res += n*A
    ans+=n
print(ans)
### BUGGY CODE ###

# 高速版input
import sys
input = sys.stdin.readline

# 二分探索
import bisect

n,m = (int(i) for i in input().split())
a = sorted([int(i) for i in input().split()])
bc = [[int(i) for i in input().split()] for i in range(m)]

for b,c in bc:
    idx = bisect.bisect_left(a,c)
    a = (a[:idx] + [c]*b + a[idx:])[b:]

print(sum(a))

### FIXED CODE ###

# 高速版input
import sys
input = sys.stdin.readline

n,m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
bc = [[int(i) for i in input().split()] for i in range(m)]

x = []
for b,c in sorted(bc, key=lambda x: x[1], reverse=True):
    x.extend([c]*b)
    if len(x) > n:
        break
        
a.extend(x)
print(sum(sorted(a,reverse=True)[:n]))
### BUGGY CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    a = [int(input().rstrip('\n')) for _ in range(m)]
    x = [0] * (n + 1)
    x[0] = 1 if 0 not in a else 0
    x[1] = 1 if 1 not in a else 0
    for i in range(2, n+1):
        if i not in a:
            x[i] = (x[i-1] + x[i-2]) % 1000000007
        else:
            x[i] = 0
    print(x[-1])


if __name__ == '__main__':
    slove()


### FIXED CODE ###

n, m = map(int, input().split())
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in [int(input()) for _ in range(m)]:
    dp[i] = -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])
### BUGGY CODE ###

N, Q = input().strip().split(' ')
S = input().strip()

for i in range(int(Q)):
    l, r = tuple(map(int, input().strip().split(' ')))
    print(S[l-1:r].count('AC'))


### FIXED CODE ###

dd = input().strip().split(' ')
N, Q = tuple(map(int, dd))
S = input().strip()

ac_indicies = []
cp = S.find('AC')
while cp != -1:
    ac_indicies.append(cp)
    cp = S.find('AC', cp + 1)

min_i = 0
ac = ac_indicies + [N]
l_index = []
for i in range(N):
    if i > ac[min_i]:
        min_i += 1
    l_index.append(min_i)

total = len(ac_indicies)
for i in range(int(Q)):
    l, r = tuple(map(int, input().strip().split(' ')))
    print(l_index[r-1] - l_index[l-1])
### BUGGY CODE ###

N, K = map(int, input().split())
XY = [list(map(int, input().split())) for i in range(N)]
ans = float('inf')
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                cnt = 0
                if (XY[i][0] >= XY[j][0]) or (XY[k][1] >= XY[l][1]):
                    continue
                for x, y in XY:
                    if (XY[i][0] <= x <= XY[j][0]) & (XY[k][1] <= y <= XY[l][1]):
                        cnt += 1
                if cnt >= K:
                    ans = min(ans, (XY[j][0]-XY[i][0]) * (XY[l][1]-XY[k][1]))

print(ans)







### FIXED CODE ###

N, K = map(int, input().split())
XY = []
YX = []
for i in range(N):
    x, y = map(int, input().split())
    XY.append([x, y, i])
    YX.append([y, x, i])
XY.sort()
YX.sort()

x_order = {}
for xo, p in enumerate(XY):
    x, y, i = p
    x_order[i] = xo

cums = [[0 for j in range(N+1)] for i in range(N+1)]
for i in range(N):
    y, x, pi = YX[i]
    xo = x_order[pi]
    for j in range(N + 1):
        cums[i + 1][j] = cums[i][j] + (1 if j > xo else 0)

ans = float('inf')

for i in range(N-1):
    for j in range(i+1, N):
        for k in range(N-1):
            for l in range(k+1, N):
                if cums[l+1][j+1] - cums[l+1][i] - cums[k][j+1] + cums[k][i] >= K:
                        ans = min(ans, (XY[j][0]-XY[i][0]) * (YX[l][0]-YX[k][0]))

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

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

ans = 0
for i in range(n):
    
    count = 0
    for j in range(i):
        if P[i] <= P[j]:
            count += 1
    if count == i:
        ans += 1
        
print(ans)

### FIXED CODE ###

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

num = 2*10**5+1
ans = 0
for i in range(n):
    if P[i] <= num:
        num = P[i]
        ans += 1
        
print(ans)
### BUGGY CODE ###

mod=10**9+7
n=int(input())
arr=list(map(int,input().split()))
blist=[0]*61
plist=[2**i for i in range(61)]
for i in range(n):
  tmp=arr[i]
  pos=0
  while tmp!=0:
    if tmp%2==1:
      blist[pos]+=1
      tmp-=1
    tmp=tmp//2
    pos+=1
ans=0
for i in range(n):
  flag=format(arr[i],'b')
  if len(flag)!=61:
    flag='0'*(61-len(flag))+flag
  flag=flag[::-1]
  for j in range(61):
    c=int(flag[j])
    if c==1:
      ans+=plist[j]*(n-blist[j])
      ans%=mod
    else:
      ans+=plist[j]*blist[j]
      ans%=mod
ans*=pow(2,mod-2,mod)
ans%=mod
print(ans)

### FIXED CODE ###

mod=10**9+7
n=int(input())
arr=list(map(int,input().split()))
blist=[0]*61
plist=[2**i for i in range(61)]
for i in range(n):
  tmp=arr[i]
  pos=0
  while tmp!=0:
    if tmp%2==1:
      blist[pos]+=1
      tmp-=1
    tmp=tmp//2
    pos+=1
ans=0
for i in range(61):
  ans+=(plist[i]*blist[i])*(n-blist[i])+(plist[i]*(n-blist[i]))*blist[i]
  ans%=mod
ans*=pow(2,mod-2,mod)
ans%=mod
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
# from numba import njit

MOD = 1000000007


# @njit
def solve(x, y, f):
    digit = 0
    for n in range(S.shape[0]):
        k = n % 6
        if S[n] == 15:
            s = 0
            for i in range(13):
                s += x[i]
            for i in range(13):
                g = f[k, i]
                y[i] = (s - x[g[0]] - x[g[1]] - x[g[2]]) % MOD
            x, y = y, x
        else:
            digit += a[k] * S[n]
    return (5 - digit) % 13, x


# @njit
def set_dp(f, c):
    for k in range(6):
        x = np.zeros(13, dtype=np.uint64)
        for m in range(c.shape[1]):
            x[c[k, m]] = 1
        count = 0
        for m in range(13):
            if x[m] == 0:
                f[k, 0, count] = m
                count += 1
        for i in range(12):
            for j in range(3):
                f[k, i + 1, j] = f[k, i, j] + 1


S = np.frombuffer(sys.stdin.buffer.read(), dtype=np.int8)
S = S[:-1][::-1] - 48

a = 10 ** np.arange(6) % 13
b = np.tile(np.arange(10), (6, 1))
c = (-a * b.T % 13).T
f = np.empty((6, 13, 3), dtype=np.uint64)
set_dp(f, c)
f %= 13
dp = np.zeros(13, dtype=np.int64)
dp[0] = 1
nex = np.zeros(13, dtype=np.int64)
m, dp = solve(dp, nex, f)
print(dp[m])

### FIXED CODE ###

import numpy as np

MOD = 1000000007
S = input()[::-1]

a = 10 ** np.arange(6) % 13
b = np.tile(np.arange(10),(6, 1))
c = a * b.T % 13
c = c.T
f = np.zeros((6, 13, 13), dtype=np.int64)
for i in range(6):
    f[i, 0, c[i]] = 1
    for j in range(12):
        f[i, j + 1] = np.roll(f[i, j], 1)

prev = np.zeros(13, dtype=np.int64)
prev[0] = 1
digit = 0

for i, c in enumerate(S):
    k = i % 6
    if c == '?':
        cur = np.dot(prev, f[k]) % MOD
        prev, cur = cur, prev
    else:
        digit += a[k] * (ord(c) - ord('0'))

m = (5 - digit) % 13
print(prev[m])
### BUGGY CODE ###

def lcs(x,y):
    x = " " + x
    y = " " + y
    c = [[0 for i in xrange(len(x))] for j in xrange(len(y))]
    for i in xrange (1,len(y)):
        for j in xrange (1,len(x)):
            if x[j] == y[i]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i][j-1],c[i-1][j])
    return max(max(c))
n = input() 
for i in xrange (n): 
    x = raw_input()
    y = raw_input() 
    print lcs(x,y)

### FIXED CODE ###

def lcs():
    x, y = raw_input(), raw_input()
    b1 = [0 for k in range(len(y)+1)]
    for i in xrange(len(x)):
        a = x[i]
        b2 = b1 + []
        for j in xrange(len(y)):
            if a == y[j]:
                b1[j+1] = b2[j] + 1
            elif b1[j+1] < b1[j]:
                b1[j+1] = b1[j]
    print max(b1)
 
n = input()
for i in xrange(n):
    lcs()
### BUGGY CODE ###

import math
n = int(input())
for i in range(1, n+1):
    ans = 0
    for x in range(1, int(math.sqrt(n+1))):
        x2 = x*x
        for y in range(1, int(math.sqrt(n+1))):
            y2 = y*y
            xy = x * y
            for z in range(1, int(math.sqrt(n+1))):
                if x2 + y2 + z*z + xy + y*z + z*x == i:
                    ans += 1
    print(ans)


### FIXED CODE ###

import math
n = int(input())
# ans = [0 for _ in range(n)]
ans = [0] * n

for x in range(1, int(math.sqrt(n+1))):
    x2 = x*x
    for y in range(1, int(math.sqrt(n+1))):
        y2 = y*y
        xy = x * y
        tmp = x2 + y2 + xy
        if tmp >= n:
            break
        for z in range(1, int(math.sqrt(n+1))):
            tmp2 = tmp + z*z + y*z + z*x
            if tmp2 > n:
                break
            try:
                ans[tmp2 - 1] += 1
                # print(x, y, z)
            except:
                pass
for i in range(n):
    print(ans[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N, Q = map(int,input().split())
G = [[] for _ in range(N)]
for i in range(N-1) :
    a, b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
ans = [0]*N
for i in range(Q) :
    pi, xi = map(int,input().split())
    ans[pi-1] += xi

def dfs(n) :
    visited[n] = 1
    for i in G[n] :
        if visited[i] == 1 :
            continue
        ans[i] += ans[n]
        dfs(i)

visited = [0]*N
dfs(0)

print(*ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N, Q = map(int,input().split())
G = [[] for _ in range(N)]
for i in range(N-1) :
    a, b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
ans = [0]*N
for i in range(Q) :
    pi, xi = map(int,input().split())
    ans[pi-1] += xi

def dfs(n) :
    visited[n] = 1
    for i in G[n] :
        if visited[i] == 1 :
            continue
        ans[i] += ans[n]
        dfs(i)

visited = [0]*N
dfs(0)

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

from fractions import gcd
from math import ceil
n,m=map(int,input().split())
a=list(map(int,input().split()))
c=len(bin(a[0]))-bin(a[0]).rfind("1")
for i in range(1,n):
  if c!=len(bin(a[i]))-bin(a[i]).rfind("1"):
    print(0)
    exit()
g=a[0]
for i in range(n-1):
   g=(g//gcd(g,a[i+1]))*(a[i+1]//gcd(g,a[i+1]))*gcd(g,a[i+1])
g//=2
print(ceil((m//g)/2))


### FIXED CODE ###

from fractions import gcd
from math import ceil
n,m=map(int,input().split())
a=list(map(int,input().split()))
c=len(bin(a[0]))-bin(a[0]).rfind("1")
for i in range(1,n):
  if c!=len(bin(a[i]))-bin(a[i]).rfind("1"):
    print(0)
    exit()
g=a[0]
for i in range(n-1):
   g=(g//gcd(g,a[i+1]))*(a[i+1]//gcd(g,a[i+1]))*gcd(g,a[i+1])
g//=2
print(ceil((m//g)/2))
### BUGGY CODE ###

import itertools

N = int(input())

lst = []
# listにN個の数値を格納
for i in range(N):
    lst.append(int(input()))

l_sum = sum(lst)

p_list = []

if l_sum % 10 == 0:
    
    # enumerate()関数を使うと、forループの中でリスト（配列）インデックス番号（カウント、順番）を取得できる
    # i にインデックス番号が入る

    for i, _ in enumerate(lst, 1):
        # permutations()を使うと 第2引数分の全パターンを取得できる
        for j in itertools.permutations(lst, r=i):  # rには1、2、3と渡される
            p_list.append(j)

    q_list = sorted(set(list(map(sum, p_list))),reverse=True)
    x = 0
    for i, item in enumerate(q_list, 1):
        if item % 10 != 0 :
            print(item)
            exit(0)
    
    if x == 0:
        print(0)

else:
    print (l_sum)




### FIXED CODE ###

N = int(input())

lst = []
# listにN個の数値を格納
for i in range(N):
    lst.append(int(input()))

lst.sort()
lstsum = sum(lst)
p_list = [ i / 10 for i in lst if i % 10 != 0 ]

if len(p_list) == 0:
    print(0)
elif lstsum % 10 != 0:
    print(lstsum)
else:
    for i in range(N):
        ans = lstsum - lst[i]
        if ans % 10 != 0:
            print(ans)
            exit(0)
### BUGGY CODE ###

N,M=map(int, input().split())

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

A.sort()
S.sort(key=lambda x: x[1], reverse=True)

X = [0]*(len(A))
idx = 0

for i in range(M):
    if idx < len(A):
        X[idx:S[i][0]] = [S[i][1]] * S[i][0]
        idx += S[i][0]

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

print(sum(A))


### FIXED CODE ###

N,M=map(int, input().split())

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

A.sort()
S.sort(key=lambda x: x[1], reverse=True)

idx = 0

for i in range(M):
    for j in range(idx, min(N, idx + S[i][0])):
        if A[j] < S[i][1]:
            A[j] = S[i][1]
            idx += 1
        else:
            break

print(sum(A))
### BUGGY CODE ###

from collections import deque
n,k = map(int,input().split())
tele = {}
a = list(map(int,input().split()))
for i in range(1,n+1):
    tele[i] = a[i-1]
lis = deque([1])
now = 1
n = 1
while tele[now] not in lis:
    lis.append(tele[now])
    now = tele[now]
p = lis.index(tele[now])
q = len(lis) - p
if k <= p:
    print(lis[k])
else:
    print(lis[(k-p)%q + p])





### FIXED CODE ###

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

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

l=[1]
di={}
di[1]=1

for i in a:
    b=a[l[-1]-1]
    if b in di:
        x=b
        break
    l.append(b)
    di[b]=1
t1=0
for j in l:
    if j==x:
        break
    else:
        t1+=1

t2=len(l)-t1
if k<=t1:
    print(l[k])

else:
    aa=(k-t1)%t2
    print(l[t1+aa])
### BUGGY CODE ###

from fractions import gcd

def main():
    lcm = lambda a, b: a * b // gcd(a, b)
    mod = 10 ** 9 + 7

    N, *A = map(int, open(0).read().split())

    L = 1
    for a in A:
        L = lcm(L, a)

    ans = 0
    for a in A:
        ans = (ans + L // a) % mod

    print(ans)

main()

### FIXED CODE ###

from fractions import gcd
from functools import reduce

def main():
    lcm = lambda a, b: a * b // gcd(a, b)
    mod = 10 ** 9 + 7

    N, *A = map(int, open(0).read().split())

    L = reduce(lcm, A)
    print(sum(L // a for a in A) % mod)

main()
### BUGGY CODE ###


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

buka = []


for i in range(N):
    b = 0
    for j in range(N-1):
        if (i+1) == A[j]:
            b += 1

    buka.append(b)
    
# 出力
for i in range(N):
    print(buka[i])



### FIXED CODE ###


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

buka = [0] * N

for i in range(N-1):
    buka[A[i]-1] += 1
    
# 出力
for i in range(N):
    print(buka[i])
### BUGGY CODE ###

import math
r,g,b,n = map(int,input().split())

ans = 0
for i in range(math.ceil(n/r)+1):
  for j in range(math.ceil(n/g)+1):
    if (n - r*i - g*j)%b == 0 and n - r*i - g*j >= 0:
      ans += 1
print(ans)

### FIXED CODE ###

import math
r,g,b,n = map(int,input().split())
 
ans = 0
for i in range(math.ceil(n/r)+1):
  for j in range(math.ceil((n-r*i)/g)+1):
    if (n - r*i - g*j)%b == 0 and n - r*i - g*j >= 0:
      ans += 1
print(ans)
### BUGGY CODE ###

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

d = sum(A)
for i in range(n):
    d = min(abs(sum(A[:i]) - sum(A[i:])), d)
print(d)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
s = sum(A)
p = 10**20
t = 0
for i in range(n):
    t += A[i]
    p = min(p, abs(s-t*2))
print(p)
### BUGGY CODE ###

n = int(input())
A = [int(input()) for i in range(n)]
ans = 1
light = 0
list = []

while True:
    if A[light] in list:
        ans = -1
        break
    elif A[light] == 2:
        break
    else:
        ans = ans + 1
        list.append(light + 1)
        light = A[light] - 1

print(ans)

### FIXED CODE ###

n = int(input())
A = [int(input()) for i in range(n)]
ans = 0
light = 1
list = [0] * n

while True:
    if light == 2:
        break
    elif list[light - 1] == 1:
        ans = -1
        break
    else:
        ans = ans + 1
        list[light - 1] = 1
        light = A[light - 1]

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

n=int(input())
table=[[0]*n for i in range(n)]
for i in range(n):
  s=input()
  for j in range(n):
    if s[j]=="1":
      table[i][j]=1
    else:
      table[i][j]=float("inf")
def warshall_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if d[i][j]==float("inf") or d[i][k]+d[k][j]==float("inf"):
          d[i][j]=min(d[i][j],d[i][k]+d[k][j])
        else:
          if d[i][j]%2!=(d[i][k]+d[k][j])%2:
            return False
          else:
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d

d=warshall_floyd(table)

if not d:
  print(-1)
else:
  ans=0
  for i in range(n):
    for j in range(i+1,n):
      ans=max(ans,d[i][j]+1)
  
  print(ans)

### FIXED CODE ###

n=int(input())
inf=float("inf")
table=[[inf]*n for i in range(n)]
for i in range(n):
  s=input()
  for j in range(n):
    if s[j]=="1":
      table[i][j]=1
    
def warshall_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if d[i][k]!=inf and d[k][j]!=inf:
          d[i][j]=min(d[i][j],d[i][k]+d[k][j])
          if d[i][j]<float("inf") and d[i][j]%2!=(d[i][k]+d[k][j])%2:
            return False
  return d

d=warshall_floyd(table)

if not d:
  print(-1)
else:
  ans=0
  for i in range(n):
    for j in range(i+1,n):
      ans=max(ans,d[i][j]+1)
  
  print(ans)
### BUGGY CODE ###

class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def nCr(self, n, r):
        r = min(n - r, r)
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def nHr(self, n, r):
        return self.nCr(n - 1 + r, r)


def main():
    MOD = 10 ** 9 + 7

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

    cl = Calc(max_value=r2 + c2 + 1, mod=MOD)
    nCr = cl.nCr

    c1_minus_1 = c1 - 1
    ans = 0
    for r_plus_1 in range(r1 + 1, r2 + 1 + 1):
        ans = (ans + nCr(r_plus_1 + c2, r_plus_1) - nCr(r_plus_1 + c1_minus_1, r_plus_1)) % MOD
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# http://drken1215.hatenablog.com/entry/2020/02/09/225000

class Calc:
    def __init__(self, *, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def factorial(self, n):
        return self.fact[n]


def main():
    mod = 10 ** 9 + 7

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

    cl = Calc(max_value=r2 + c2 + 1, mod=mod)

    ret = 0
    for r in range(r1, r2 + 1):
        ret += cl.combination(r + c2 + 1, r + 1)
        ret -= cl.combination(r + (c1 - 1) + 1, r + 1)
        ret %= mod

    print(ret)


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

def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

axis = val(0)

ng = 0
ok = n - 1

while ng + 1 < ok:
    mid = (ng + ok) // 2
    sex = val(mid)
    if sex == axis:
        ng = mid
    else:
        ok = mid

print(ng, flush=True)
exit(0)


### FIXED CODE ###

def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)
r_sex = val(n - 1)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != l_sex:
        right = mid
        r_sex = sex
    elif (mid - left) % 2 == 1 and sex == l_sex:
        right = mid
        r_sex = sex
    else:
        left = mid
        l_sex = sex

print(left, flush=True)
exit(0)
### BUGGY CODE ###

X = input()

while X != ''.join(X.split('ST')):
    X = ''.join(X.split('ST'))

print(len(X))


### FIXED CODE ###

from collections import deque

X = input()
stack = deque([X[0]])
for i in range(1, len(X)):
    if X[i] == 'S':
        stack.appendleft(X[i])

    if X[i] == 'T':
        if stack:
            check = stack.popleft()
            if check == 'T':
                stack.appendleft(check)
                stack.appendleft(X[i])
        else:
            stack.appendleft(X[i])

print(len(stack))
### BUGGY CODE ###

N,M = map(int, input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i], B[i] = map(int, input().split())
    
parent = [0]*(N+1)
parent[0] = -1
parent[1] = -1

nextroom = [1]
for j in range(N):
    for i in range(M):
        if A[i]==nextroom[0] and parent[B[i]]==0:
            nextroom.append(B[i])
            parent[B[i]] = A[i]
        if B[i]==nextroom[0] and parent[A[i]]==0:
            nextroom.append(A[i])
            parent[A[i]] = B[i]
    nextroom.pop(0)
    
if parent.count(0)==0:
    print('Yes')
    for i in range(2,len(parent)):
        print(parent[i])
else:
    print('No')

### FIXED CODE ###

from collections import deque

N,M = map(int, input().split())

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

G = {i:[] for i in range(N+1)}
for a,b in AB:
    G[a].append(b)
    G[b].append(a)
    
parent = [0]*(N+1)
parent[0]==-1
parent[1]==-1
q = deque()
q.append(1)
while len(q)>0:
    room = q.popleft()
    child = G[room]
    
    for i in child:
        if parent[i] == 0:
            parent[i] = room
            q.append(i)
    
    
if min(parent[2:])==0:
    print('No')
else:
    print('Yes')
    for i in parent[2:]:
        print(i)