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

import numpy as np
S = input()
mod = 10 ** 9 + 7

n = len(S)
a = S[-1]
x = np.zeros(13, int)
l = [1, 10, 9, 12, 3, 4]
l = [[i * l_ % 13 for i in range(1, 10)] for l_ in l]
li = 1
if a == "?":
    x[0:10] += 1
else:
    x[int(a)] += 1
for s in S[-2::-1]:
    x_ = np.zeros(13, int)
    if s == "?":
        x_ += x
        for v in l[li]:
            x_[v:] += x[:-v]
            x_[:v] += x[-v:]
    else:
        if s == "0":
            x_ += x
        else:
            v = l[li][int(s) - 1]
            x_[v:] += x[:-v]
            x_[:v] += x[-v:]
    x_ %= mod
    if li == 5:
        li = 0
    else:
        li += 1
    x = x_
print(x[5])

### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


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

import sys
input = sys.stdin.readline

from fractions import gcd

N,M=map(int,input().split())
#List=list(map(lambda x:int(x)/2,input().split()))
List=list(map(int,input().split()))

def main():
    LCM=1
    cut2count=0
    a=List[0]/2
    while a%2==0:
        a/=2
        cut2count+=1

    for i in List:
        i/=2
        LCM*=i/gcd(LCM,i)
            
        cut2countb=0
        b=i
        while b%2==0:
            b/=2
            cut2countb+=1
        if cut2count!=cut2countb:
            print(0)
            exit()


    #for i in List:
    #   if LCM/i%2==0:
    #      print(0)
    #     exit()

    print(int(M//(LCM*2)+M%(LCM*2)//LCM))


if __name__ == '__main__':
    main()

### FIXED CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
List=list(map(lambda x:int(x)//2,map(int, set(input().split()))))

def main():
    LCM=1

    for i in List:
        LCM*=i//gcd(LCM,i)

    for i in List:
        if LCM//i%2==0:
            print(0)
            exit()

    print(int(M//(LCM*2)+M%(LCM*2)//LCM))


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

import copy
n = int(input())
a = list(map(int, input().split()))

l = a.copy()

a.sort()
ans = 0
i = 0
while True:
    cnt = 0
    while a[i + cnt] == a[i]:
        cnt += 1
        if i + cnt == n:
            break
    ans += cnt*(cnt - 1)//2
    i += cnt
    if i == n:
        break

for i in range(n):
    num = l[i]
    del l[i]
    ac = l.count(num)
    print(ans - ac)
    l.insert(0, num)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))

d = Counter(a)
key = d.keys()
ans = 0
for i in key:
    ans += (d[i]*(d[i]  - 1))//2

for i in a:
    print(ans - d[i] + 1)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


n = inp()
a = inpl()
g = 1
res = 0
for i in a:
    g = i*g//fractions.gcd(i,g)
for i in a:
    res += g//i
    res %= mod
print(res)


### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


n = inp()
a = inpl()
g = 1
res = 0
for i in a:
    g = i*g//fractions.gcd(i,g)
for i in a:
    res += g//i
print(res%mod)
### BUGGY CODE ###

q=int(input())
n=10**5

work=[1 if i%2==1 else 0 for i in range(n+1)]
primes=[2]
lst=[0]*(n+1)
work[1]==0

for i in range(3,n,2):
    if not work[i]: continue
    primes.append(i)
    index=1
    while i*index<=n:
        work[i*index]=0
        index+=1

for i in primes[1:]:
    if (i+1)//2 in primes:
        lst[i]=1

for _ in range(q):
    left,right=map(int,input().split())
    print(sum(lst[left:right+1]))


### FIXED CODE ###

q=int(input())
n=10**5

work=[1 if i%2==1 else 0 for i in range(n+1)]
primes=[2]
lst=[0]*(n+1)
work[1]==0

for i in range(3,n,2):
    if not work[i]: continue
    primes.append(i)
    index=1
    while i*index<=n:
        work[i*index]=0
        index+=1

for i in primes[1:]:
    if (i+1)//2 in primes:
        lst[i]=1

for i in range(3,n+1):
    lst[i]+=lst[i-1]

for _ in range(q):
    left,right=map(int,input().split())
    print(lst[right]-lst[left-1])
### BUGGY CODE ###

import heapq
n=int(input())
a=[-int(input()) for i in range(n)]
for i in range(n):
  x=a[:i]+a[i+1:]
  heapq.heapify(x)
  print(-heapq.heappop(x))

### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
b=[a[i] for i in range(n)]
b.sort()
m=b[n-1]
m2=b[n-2]
for i in range(n):
  if a[i]==m:
    print(m2)
  else:
    print(m)
### BUGGY CODE ###

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

A_sort = sorted(A)
F_sort = sorted(F,reverse=True)

l = -1
r = 0
for i in range(N):
    r = max(r,A_sort[i]*F_sort[i])

def judge(c):
    s = 0
    for i in range(N):
        s += max(A_sort[i]-c//F_sort[i],0)
    return s <= K

while r-l > 1:
    c = (l+r)//2
    if judge(c):
        r = c
    else:
        l = c
print(r)

### FIXED CODE ###

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

A_sort = sorted(A)
F_sort = sorted(F,reverse=True)

l = -1
r = 0
for i in range(N):
    r = max(r,A_sort[i]*F_sort[i])

def judge(c):
    s = 0
    for i in range(N):
        s += max(A_sort[i]-c//F_sort[i],0)
    return s <= K

while r-l > 1:
    c = (l+r)//2
    if judge(c):
        r = c
    else:
        l = c
print(r)
### BUGGY CODE ###

import sys
input=lambda:sys.stdin.readline().rstrip()
r,c,k=map(int,input().split())
dp=[[(c+1)*[0]for _ in range(r+1)]for _ in range(4)]
p=[c*[0]for _ in range(r)]
for _ in range(k):
  rr,cc,u=map(int,input().split())
  rr-=1
  cc-=1
  p[rr][cc]=u
ans=0
for j in range(1,r+1):
  for k in range(1,c+1):
    dp[0][j][k]=max(dp[0][j-1][k],dp[0][j][k-1])
    for i in range(1,4):
      dp[i][j][k]=max(dp[i][j][k],dp[0][j-1][k],dp[1][j-1][k],dp[2][j-1][k],dp[3][j-1][k],dp[i][j][k-1])
      if p[j-1][k-1]:
        dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+p[j-1][k-1],max(dp[0][j-1][k],dp[1][j-1][k],dp[2][j-1][k],dp[3][j-1][k])+p[j-1][k-1])
print(max(max(max(j)for j in i)for i in dp))

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
r,c,k=map(int,input().split())
dp=[[(c+1)*[0]for _ in range(r+1)]for _ in range(4)]
p=[c*[0]for _ in range(r)]
for _ in range(k):
  rr,cc,u=map(int,input().split())
  rr-=1
  cc-=1
  p[rr][cc]=u
ans=0
#for i in p:print(i)
for j in range(1,r+1):
  for k in range(1,c+1):
    dp[0][j][k]=max(dp[0][j-1][k],dp[0][j][k-1])
    for i in range(1,4):
      dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k],dp[i][j][k-1])
      if p[j-1][k-1]:
        dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+p[j-1][k-1],dp[i][j-1][k]+p[j-1][k-1])
    for i in range(1,4):
      dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k])
      ans=max(ans,dp[i][j][k])
  for k in range(1,c+1):
    t=max(dp[0][j][k],dp[1][j][k],dp[2][j][k],dp[3][j][k])
    dp[0][j][k]=dp[1][j][k]=dp[2][j][k]=dp[3][j][k]=t
print(ans)
#for i in dp:
#  print("---")
#  for j in i:print(j)
### BUGGY CODE ###

from functools import reduce
import operator
n = int(input())
a = list(map(int, input().split()))
ans = reduce(operator.mul, a, 1)
if ans <= 10**18:
    print(ans)
else:
    print(str(-1))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1;
for i in range(n):
    if ans > 10**18:
        break
    ans *= a[i]
if 0 in a:
    print(0)
elif ans <= 10**18:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

n = int(input())
list = [int(x) for x in input().split()]
ans = []
count = 0
for  i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if (list[i] < list[j] + list[k]) and (list[j] < list[i] + list[k]) and (list[k] < list[i] + list[j]):
                count+= 1
print(count)


### FIXED CODE ###

from bisect import bisect_left

count = 0
n = int(input())
list = sorted([int(x) for x in input().split()])

for i in range(n):
    for j in range(i + 1, n) :
        sum = list[i] + list[j]
        a = bisect_left(list,sum)
        count += a - j - 1
print(count)
### BUGGY CODE ###

n = int(input())

g = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    g[u - 1][v - 1] = w
    g[v - 1][u - 1] = w

color = [-1] * n
dist = [0] * n

def dfs(v):
    for next_v in range(n):
        if color[next_v] == -1 and g[v][next_v] != 0:
            dist[next_v] = dist[v] + g[v][next_v]
            color[next_v] = dist[next_v] % 2
            dfs(next_v)

# 0を始点として各点までの距離を求める
color[0] = 0
dfs(0)

for c in color:
    print(c)

### FIXED CODE ###

n = int(input())

g = [[] for _ in range(n)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    g[u - 1].append((v - 1, w))
    g[v - 1].append((u - 1, w))

color = [-1] * n
dist = [0] * n

import queue
def dfs(v):
    color[v] = dist[v] % 2
    q = queue.LifoQueue()
    q.put(v)

    while not q.empty():
        vv = q.get()
        for next_v in g[vv]:
            if color[next_v[0]] == -1 and next_v[1] != 0:
                dist[next_v[0]] = dist[vv] + next_v[1]
                color[next_v[0]] = dist[next_v[0]] % 2
                q.put(next_v[0])

# 0を始点として各点までの距離を求める
dfs(0)

for c in color:
    print(c)
### BUGGY CODE ###

from itertools import permutations
def read(): return list(map(int, input().split()))

INF = 1145141919

def wf(d):
    N = len(d[0])
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


def calc_dist(p, d):
    dist = 0
    for i in range(len(p) - 1):
        dist += d[p[i]][p[i + 1]]
    return dist


def main():
    N, M, R = read()
    r = map(lambda x: x - 1, sorted(read()))
    d = [[INF for i in range(N)] for j in range(N)]

    for i in range(M):
        a, b, c, = read()
        a -= 1
        b -= 1
        d[a][b] = d[b][a] = c

    d = wf(d)

    min_dist = INF
    for p in list(permutations(r)):
        min_dist = min(min_dist, calc_dist(p, d))

    print(min_dist)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from itertools import permutations
def read(): return list(map(int, input().split()))


INF = 114514810


def wf(d):
    N = len(d[0])
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d


def calc_dist(p, d):
    dist = 0
    for i in range(len(p) - 1):
        if d[p[i]][p[i + 1]] >= INF:
            return INF
        dist += d[p[i]][p[i + 1]]
    return dist


def main():
    N, M, R = read()
    r = map(lambda x: x - 1, sorted(read()))
    d = [[INF for i in range(N)] for j in range(N)]

    for i in range(M):
        a, b, c, = read()
        a -= 1
        b -= 1
        d[a][b] = d[b][a] = c

    d = wf(d)

    min_dist = INF
    for p in list(permutations(r)):
        min_dist = min(min_dist, calc_dist(p, d))

    print(min_dist)


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

t = 0
SENTINEL = 1e+9


def sort(a, b):
    global t
    a.append(SENTINEL)
    b.append(SENTINEL)
    i, j = 0, 0
    while i < len(a)-1 or j < len(b)-1:
        t += 1
        if a[i] < b[j]:
            yield a[i]
            i += 1
        else:
            yield b[j]
            j += 1


def merge(a, left, mid, right):
    left_list, right_list = a[left:mid], a[mid:right]
    for index, value in zip(range(left, right), sort(left_list, right_list)):
        a[index] = value


def merge_sort(a, left, right):
    if right-left > 1:
        mid = (left + right) // 2
        merge_sort(a, left, mid)
        merge_sort(a, mid, right)
        merge(a, left, mid, right)


def main():
    global t
    input()
    a = [int(i) for i in input().split()]
    merge_sort(a, 0, len(a))
    print(*a)
    print(t)


if __name__ == '__main__':
    main()



### FIXED CODE ###

SENTINEL = 1e+9
t = 0


def Merge(A, left, mid, right):
    global t
    n1 = mid - left
    n2 = right - mid
    L, R = A[left:left+n1], A[mid:mid+n2]
    L.append(SENTINEL)
    R.append(SENTINEL)
    i, j = 0, 0
    for k in range(left, right):
        t += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


def Merge_Sort(A, left, right):
    if left+1 < right:
        mid = (left + right) // 2
        Merge_Sort(A, left, mid)
        Merge_Sort(A, mid, right)
        Merge(A, left, mid, right)


def main():
    global t
    input()
    A = [int(i) for i in input().split()]
    Merge_Sort(A, 0, len(A))
    print(*A)
    print(t)


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

from bisect import bisect_left as bl
A,B,Q=map(int,input().split())
S=[]
T=[]
X=[]
for i in range(A):
    S.append(int(input()))
for i in range(B):
    T.append(int(input()))
def rl(X,a):
    ind=bl(X,a)
    if ind>=len(X):
        return ind-1
    return ind
def ll(X,a):
    ind=bl(X,a)-1
    if ind<0:
        return ind+1
    return ind
def l(X,a):
    ind=bl(X,a)
    if ind>=len(X):
        ind1=ind-1
        return (ind1,ind1)
    elif ind-1<0:
        return (ind,ind)
    else:
        return (ind,ind-1)
t=[]
for i in range(A):
    ind1,ind2=l(T,S[i])
    mi=min(abs(T[ind1]-S[i]),abs(T[ind2]-S[i]))
    t.append(mi)
"""
    if abs(T[rl(T,S[i])]-S[i])>=abs(T[ll(T,S[i])]-S[i]):
        t.append(abs(T[ll(T,S[i])]-S[i]))
    else:
        t.append(abs(T[rl(T,S[i])])-S[i])
"""
s=[]
for i in range(B):
    ind1,ind2=l(S,T[i])
    mi=min(abs(S[ind1]-T[i]),abs(S[ind2]-T[i]))
    s.append(mi)
"""
    if abs(S[rl(S,T[i])]-T[i])>=abs(S[ll(S,T[i])]-T[i]):
        s.append(abs(S[ll(S,T[i])]-T[i]))
    else:
        s.append(abs(S[rl(S,T[i])])-T[i])
"""
for i in range(Q):
    x=int(input())
    a=rl(S,x)
    a=t[a]+abs(S[a]-x)

    b=ll(S,x)
    b=t[b]+abs(S[b]-x)

    c=rl(T,x)
    c=s[c]+abs(T[c]-x)

    d=ll(T,x)
    d=s[d]+abs(T[d]-x)

    print(min(a,b,c,d))


### FIXED CODE ###

from bisect import bisect_left as bl
A,B,Q=map(int,input().split())
S=[]
T=[]
X=[]
INF=10**18
S.append(-INF)
T.append(-INF)
for i in range(A):
    S.append(int(input()))
for i in range(B):
    T.append(int(input()))
S.append(INF)
T.append(INF)
for i in range(Q):
    x=int(input())
    b,d=bl(S,x),bl(T,x)
    res=INF
    for s in [S[b-1],S[b]]:
        for t in [T[d-1],T[d]]:
            d1,d2=abs(s-x)+abs(t-s),abs(t-x)+abs(s-t)
            res=min(res,d1,d2)
    print(res)
### BUGGY CODE ###

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


if n < b:
    print((a*n)//b)
    exit()

num = n//b
ans = 0

for i in range(1,num+1):
    num2 = i*b-1
    #print(num2)
    temp = (a*num2)//b - a * (num2//b)
    ans = max(temp,ans)

print(max(ans,(a*n)//b - a * (n//b)))


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():

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

    if n < b:
        print((a*n)//b)
        exit()

    num = n//b

    ans = (a*(b-1))//b
    print(max(ans,(a*n)//b - a * (n//b)))

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

import sys
import operator

input=sys.stdin.readline

def main():
    n,m = map(int, input().split())
    a = [int(i) for i in input().split()]
    sousa = []
    d = []
    for _ in range(m):
        sousa.append([int(i) for i in input().split()])

    a.sort()
    
    sousa.sort(key=operator.itemgetter(1))

    for i in sousa:
        d.extend([i[1]] * i[0])

    dIdx = len(d) - 1

    for i in range(len(a)):
        if a[i] < d[dIdx]:
            a[i] = d[dIdx]
            dIdx -= 1
            if dIdx < 0:
                break

    print(sum(a))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import operator

input=sys.stdin.readline

def main():
    n,m = map(int, input().split())
    a = [int(i) for i in input().split()]
    sousa = []
    d = []
    for _ in range(m):
        sousa.append([int(i) for i in input().split()])

    a.sort()
    
    sousa.sort(key=operator.itemgetter(1), reverse = True)

    for i in sousa:
        d.extend([i[1]] * i[0])
        if len(d)>n:
            break

    dIdx = 0
    dLen = len(d)

    for i in range(len(a)):
        if a[i] < d[dIdx]:
            a[i] = d[dIdx]
            dIdx += 1
            if dIdx >= dLen:
                break

    print(sum(a))

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

n = int(input())
s = input()

ans = 3*(10**5)
for i in range(n):
  
  east = s.count('W', 0, i-1) if i else 0
  west = s.count('E', i+1) if not i==n-1 else 0
  ans = east+west if ans>east+west else ans
  
print(ans)


### FIXED CODE ###

n = int(input())
s = input()

to_east = 0
to_west = s.count('E', 1)
ans = to_east+to_west

for i in range(1, n):
  if s[i-1]=='W':
    to_east += 1
  if s[i]=='E':
    to_west -= 1
  ans = to_east+to_west if ans>to_east+to_west else ans
  
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

Qs = 3 if S[0] == '?' else 1
A = [0] * N
AB = [0] * N
ABC = [0] * N
if S[0] in 'A?':
    A[0] = 1
for i, s in enumerate(S[1:], 1):
    factor = 3 if s == '?' else 1
    A[i] = A[i - 1] * factor % MOD
    AB[i] = AB[i - 1] * factor % MOD
    ABC[i] = ABC[i - 1] * factor % MOD
    if s in 'A?':
        A[i] += Qs
    if s in 'B?':
        AB[i] += A[i - 1]
    if s in 'C?':
        ABC[i] += AB[i - 1]
    if s == '?':
        Qs *= 3

ans = ABC[-1] % MOD
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0, 0, 0, 0]
dp[0] = 1

for s in S:
    factor = 3 if s == '?' else 1
    for j, c in zip([2, 1, 0], 'CBA'):
        dp[j + 1] = dp[j + 1] * factor % MOD
        if s == c or s == '?':
            dp[j + 1] += dp[j]
    if s == '?':
        dp[0] = (dp[0] * 3) % MOD

ans = dp[-1] % MOD

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

n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 1
mod = 998244353
for i in range(n):
    for j in range(s+1):
        dp[i+1][j] = dp[i][j]*2%mod
        if a[i]<=j: dp[i+1][j] = (dp[i+1][j]+dp[i][j-a[i]])%mod
        dp[i+1][j] %= mod
print(dp[n][s])

### FIXED CODE ###

n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 1
mod = 998244353
for i in range(n):
    for j in range(s+1):
        dp[i+1][j] = dp[i][j]*2%mod
        if a[i]<=j: dp[i+1][j] = (dp[i+1][j]+dp[i][j-a[i]])%mod
        dp[i+1][j] %= mod
print(dp[n][s])
### BUGGY CODE ###

s = input()

count = 0
 
def str_del(str,index):
    str = str[:index]+str[index+1:]
    return str
 
string = s
can_remove = True
while can_remove:
  new_text = ''
  search_count = string.count('10')
  if search_count > 0:
    new_text = string.replace('10', '', search_count)
  else:
    search_count = string.count('01')
    if search_count > 0:
      new_text = string.replace('01', '', search_count)

  if new_text != string:
    string = new_text
    count += search_count * 2
    can_remove = True
  else:
    can_remove = False
 
print(count)


### FIXED CODE ###

s = input()

count0 = s.count('0')
count1 = s.count('1')
print(min(count0, count1) * 2)
### BUGGY CODE ###

import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  
r1, c1, r2, c2 = [int(i) for i in input().split()]

def calc(r, c):
    a = comb(r + c + 2, r + 1) - r - c - 2
    b = r * (r + 3) / 2

    if c == 1:
        return b
    else:
        return a

result = calc(r2, c2) - calc(r2, c1 - 1) - calc(r1 - 1, c2) + calc(r1 - 1, c1 - 1)

print(result %  (10**9+7))

### FIXED CODE ###

from operator import mul
from functools import reduce

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

mod = 10**9+7 #出力の制限
N = 3 * 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
    
    
    
r1, c1, r2, c2 = [int(i) for i in input().split()]
 
def calc(r, c):
    a = comb(r + c + 2, r + 1, mod) - r - c - 2
    b = r * (r + 3) / 2
 
    if c == 1:
        return b
    else:
        return a
 
result = calc(r2, c2) - calc(r2, c1 - 1) - calc(r1 - 1, c2) + calc(r1 - 1, c1 - 1)
result %= mod
if result < 0:
  result += mod
print(result)
### BUGGY CODE ###

import sys


fin = sys.stdin.readline
MOD = 10 ** 9 + 7
S = fin().rstrip("\n")[::-1]
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
for i, c in enumerate(S, start=1):
    base = 10 ** (i - 1) % 13
    if c != '?':
        d = int(c) * base % 13
        for r in range(13):
            c = (d + r) % 13
            dp[i][c] += dp[i - 1][r]
            dp[i][c] %= MOD
    else:
        for d in range(10):
            d = d * base % 13
            for r in range(13):
                c = (d + r) % 13
                dp[i][c] += dp[i - 1][r]
                dp[i][c] %= MOD
print(dp[-1][5])


### FIXED CODE ###

# import sys


# fin = sys.stdin.readline
MOD = 10 ** 9 + 7
S = input()[::-1]
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
for i, c in enumerate(S, start=1):
    base = pow(10, i - 1, 13)
    if c != '?':
        d = int(c) * base % 13
        for r in range(13):
            c = (d + r) % 13
            dp[i][c] += dp[i - 1][r]
            dp[i][c] %= MOD
    else:
        for d in range(10):
            d = d * base % 13
            for r in range(13):
                c = (d + r) % 13
                dp[i][c] += dp[i - 1][r]
                dp[i][c] %= MOD
print(dp[-1][5])
### BUGGY CODE ###

K,S=map(int,input().split())
res=0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k==S:
                res+=1

print(res)


### FIXED CODE ###

K,S=map(int,input().split())
res=0
for i in range(K+1):
    for j in range(K+1):
        if S-i-j>=0 and S-i-j<=K:
            res+=1

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

import bisect
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
for i in range(M):
  B = A[-1]//2
  A=A[:N-1]
  bisect.insort_left(A, B)
  #print(A)
print(sum(A))

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=list(map(lambda x:int(x)*(-1),input().split()))
heapq.heapify(A) #落としたりするのもO(N)かかってしまうのでHeapで実装
#A=[i for i in range(N)]
for i in range(M):
  B = heapq.heappop(A)
  heapq.heappush(A,-1*(-1*B//2))
  #print(A)
print(-sum(A))