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

N,M = map(int, input().split())
L,R = map(int, input().split())
ans = set(list(range(L,R+1)))

for _ in range(M-1):
    L,R = map(int, input().split())
    gate = set(range(L,R+1))
    ans &= gate

print(len(ans))    


### FIXED CODE ###

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

for _ in range(M-1):
    l,r = map(int, input().split())
    if R>r:
        R = r
    if L<l:
        L = l

if (R-L+1)>0:
    print(R-L+1)
else:
    print(0)
### BUGGY CODE ###

import sys
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            ans += 1
s = [["#"] + i + ["#"] for i in s]
s = [["#" for i in range(w+2)]] + s + [["#" for i in range(w+2)]]
pos = [[1, 1, 0]]
for i in range(h*w):
  for j in range(len(pos)):
    x, y, cnt = pos[j]
    if x == h and y == w:
        print(ans-(cnt+1))
        sys.exit()
    s[x][y] = "~"
    if s[x-1][y] == ".":
        pos.append([x-1, y, cnt+1])
    if s[x+1][y] == ".":
        pos.append([x+1, y, cnt+1])
    if s[x][y-1] == ".":
        pos.append([x, y-1, cnt+1])
    if s[x][y+1] == ".":
        pos.append([x, y+1, cnt+1])
print(-1)

### FIXED CODE ###

import sys
H,W=map(int,input().split())
L = [[0 for j in range(W)] for i in range(H)]
c=0
for i in range(H):
  a=list(input())
  c+=a.count(".")
  L[i]=a
#幅優先探索？
subete=[[0,0]]
ans = [[] for i in range(H*W+1)]
ans[0].append([0,0])
for i in range(H*W+1):
  for j in range(len(ans[i-1])):
    a,b=ans[i-1][j][0],ans[i-1][j][1]
    if a+1!=H:
      if [a+1,b] not in subete and L[a+1][b]==".":
        ans[i].append([a+1,b])
        subete.append([a+1,b])
    if a!=0:
      if [a-1,b] not in subete and L[a-1][b]==".":
        ans[i].append([a-1,b])
        subete.append([a-1,b])
    if b+1!=W:
      if [a,b+1] not in subete and L[a][b+1]==".":
        ans[i].append([a,b+1])
        subete.append([a,b+1])
    if b!=0:
      if [a,b-1] not in subete and L[a][b-1]==".":
        ans[i].append([a,b-1])
        subete.append([a,b-1])
  if [H-1,W-1] in subete:
    print(c-i-1)
    sys.exit()
print(-1)
### BUGGY CODE ###

N,W = map (int,input().split()) 
dp = [[0 for i in range(W + 1)] for j in range(N+1)]
weight = []
value = []
for i in range(N):
    w,v = map( int, input().split() )
    weight.append(w)
    value.append(v)

for i in range(1,N+1):
    for j in range(0,W+1):
        if j - weight[i-1] >= 0:
            dp[i][j] = max( dp[i-1][ j - weight[i-1] ] + value[i-1], dp[i][j])
        dp[i][j] = max(dp[i][j],dp[i-1][j])
        
print(dp[N][W])

### FIXED CODE ###

N,W = map (int,input().split()) 
dp = [[0 for i in range(W + 1)] for j in range(N+1)]
weight = []
value = []
for i in range(N):
    w,v = map( int, input().split() )
    weight.append(w)
    value.append(v)

for i in range(1,N+1):
    for j in range(0,W+1):
        if j - weight[i-1] >= 0:
            dp[i][j] = max( dp[i-1][ j - weight[i-1] ] + value[i-1], dp[i][j])
        dp[i][j] = max(dp[i][j],dp[i-1][j])
        
print(dp[N][W])
### BUGGY CODE ###

N = int(input())
s = []
for i in range(N):
    s.append(list(input()))

[s[i].sort() for i in range(len(s))]

cnt = 0
for i in s:
    for j in s:
       if i == j:
        cnt += 1
        
cnt = (cnt - N)//2

print(cnt)

### FIXED CODE ###

from collections import Counter
import math

N = int(input())
s = []
for i in range(N):
    s.append(list(input()))

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

[s[i].sort() for i in range(len(s))]

s = [' '.join(s[i]) for i in range(len(s))]
mycounter = Counter(s)
mycounter = list(mycounter.values())

mycounter = [mycounter[i] for i in range(len(mycounter)) if mycounter[i] > 1]
mycounter = [combinations_count(mycounter[i], 2) for i in range(len(mycounter))]

print(sum(mycounter))
### BUGGY CODE ###

a, b, n = map(int, input().split())
ans = 0
for i in range(1, min(n, b)+1):
    ans = max(ans, int(a*i/b)-a*int(i/b))
print(ans)

### FIXED CODE ###

a, b, n = map(int, input().split())
x = min(b-1, n)
print(int(a*x/b)-a*int(x/b))
### BUGGY CODE ###

N=int(input())
nn=N
import math
sq=round(math.sqrt(N))+1

i=2
ans=0
count1=0
count2=1
while sq>=i:
    if nn%i==0:
        nn//=i
        count1+=1
        if count1==count2:
            ans+=1
            count2+=1
            count1=0
            sq=N//i
    else:
        i+=1
        count1=0
        count2=1

if ans==0 and N>=2:
    ans+=1

print(ans)

### FIXED CODE ###

N=int(input())
nn=N
import math
sq=round(math.sqrt(N))+1

i=2
ans=0
count1=0
count2=1
while sq>=i:
    if nn%i==0:
        nn//=i
        count1+=1
        if count1==count2:
            ans+=1
            count2+=1
            count1=0
    else:
        i+=1
        count1=0
        count2=1

if nn>sq:
    ans+=1

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

a = int(input())
l = list(map(int,input().split()))
MOD = 998244353
dp = [0]*a
for i in l:
    dp[i]+=1
res = 1
# print(dp)
if dp[0] != 1:
    print(0)
    exit()

for i in l[1:]:
    # print(i)
    res*=dp[i-1]

print(res%MOD)

### FIXED CODE ###

a = int(input())
l = list(map(int,input().split()))
MOD = 998244353
dp = [0]*a
for i in l:
    dp[i]+=1
res = 1
# print(dp)
if dp[0] != 1 and l[0]!=0:
    print(0)
    exit()

for i in l[1:]:
    # print(i)
    res*=dp[i-1]
    res%=MOD

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

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

li,ri = 0,0
ans = 1
xor = 0
add = 0
for li in range(N-1):
    ri = li+1
    xor = A[li]
    add = A[li]
    ans += 1
    while ri < N and li <= ri:
        if xor ^ A[ri] == add + A[ri]:
            xor ^= A[ri]
            add += A[ri]
            ri += 1
            ans += xor == add
            # print(f'2   li:{li} ri:{ri} {A[li:ri]} ans:{ans} xor:{xor} add:{add}')
        else:
            break

print(ans)

### FIXED CODE ###

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

li,ri = 0,0
ans = 0
xor = A[li]
add = A[li]
while ri < N and li <= ri:
    if xor == add:
        ans += ri - li +1
        ri += 1
        if ri < N:
            xor ^= A[ri]
            add += A[ri]
    else:
        if li < N:
            xor ^= A[li]
            add -= A[li]
        li += 1

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

n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in range(n):
    ans *= a[i]
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

import math
import copy
import re
mod = 10**9+7

n = int(input())
neko = 1
for i in range(n):
    neko *= (i+1)
print(neko%mod)

### FIXED CODE ###

import math
import copy
import re
mod = 10**9+7

n = int(input())
neko = math.factorial(n)
print(neko%mod)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC=[]
for i in range (0, Q):
    BC.append([int(i) for i in input().split()])
"""
for bc in BC:
    bc = [int(i) for i in bc]
"""
#print(BC)
sum = sum(A)

for bc in BC:
    count = 0
    yoso = set(A)
    if bc[0] in yoso:
        for i in range(0,len(A)):
            if A[i] == bc[0]:
                A[i] = bc[1]
                count += 1
    #  print("A:",A)
        sum += (bc[1]-bc[0])*count
    print (sum)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC=[]
for i in range (0, Q):
    BC.append([int(i) for i in input().split()])

#print(BC)
yoso_count=[]
for i in range(1,10**5+1):
    yoso_count.append([i,0])

sum = 0
for a in A:
    yoso_count[int(a)-1][1] += 1
    sum += a

#print(yoso_count,sum)

for bc in BC:
    sum += (bc[1] - bc[0])*yoso_count[bc[0]-1][1]
    yoso_count[bc[1]-1][1] += yoso_count[bc[0]-1][1]
    yoso_count[bc[0]-1][1] = 0
    print(sum)
### BUGGY CODE ###

nums = input().split()

N = int(nums[0])
M = int(nums[1])

sum = 0

while N > 0:
    if M >= 2:
        sum += 1
        M -= 2
        N -= 1

while M >= 4:
    sum += 1
    M -= 4

print(sum)

### FIXED CODE ###

nums = input().split()

N = int(nums[0])
M = int(nums[1])

sum = 0

if 2*N <= M:
    sum += N
    M -= 2*N
    if M >= 4:
        sum += M // 4
else:
    sum += M // 2    

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

N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]

Possible = True
NoNeed = set()
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            a, b, c = A[i][j], A[j][k], A[i][k]
            if a+b>=c and b+c>=a and c+a>=b:
                if a+b==c:
                    NoNeed |= {(i, k)}
                elif b+c==a:
                    NoNeed |= {(i, j)}
                elif c+a == b:
                    NoNeed |= {(j, k)}
            else:
                Possible = False
                break 

if Possible:
    Total = 0
    for i in range(N):
        Total += sum(A[i])
    Total //= 2
    for a in NoNeed:
        Total -= A[a[0]][a[1]]
    print(Total)
else:
    print(-1)

### FIXED CODE ###

import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

from heapq import heappush,heappop
MOVE = [[1,4],[0,2,5],[1,3,6],[2,7],[0,5],[1,4,6],[2,5,7],[3,6]]
GOAL = "01234567"
def h(field):    
    ret = 0
    for p,n in enumerate(map(int,field)):
        ret += dist(p,n)
    return ret
def dist(num,place):
    return abs(num%4-place%4)+(num/5+place/5)%2 #width+height
def swap(field,a,b):
    tmp = [f for f in field]
    tmp[a],tmp[b] = tmp[b],tmp[a]
    return "".join(tmp)

while True:
    try:
        field = raw_input().replace(" ","")    
    except:
        break
    hq = []
    visited = {field:True}
    heappush(hq,[0,0,field])
    while len(hq) != 0:
        f,g,field = heappop(hq)
        if field == GOAL:
            print g
            break    
        a = field.find("0")
        for b in MOVE[a]:
            tmp = swap(field,a,b)
            if tmp not in visited:
                visited[tmp] = True
                heappush(hq,[h(field)+g,g+1,tmp])

### FIXED CODE ###

# -*- coding: utf-8 -*-
#与えられるパズルの数は1000以下です
MOVE = [[1,4],[0,2,5],[1,3,6],[2,7],[0,5],[1,4,6],[2,5,7],[3,6]]
ans = {"01234567":0}
def swap(field,a,b):
    tmp = list(field)
    tmp[a],tmp[b] = tmp[b],tmp[a]
    return "".join(tmp)

def BFS():
    global ans
    q = [[0,"01234567"]]
    while len(q) != 0:
        g, field = q.pop(0)
        a = field.find("0")
        for b in MOVE[a]:
            tmp = swap(field,a,b)
            if not tmp in ans:
                ans[tmp] = g+1
                q.append([g+1,tmp])

BFS()
while True:
    try:
        print ans[raw_input().replace(" ","")]
    except:
        break
### BUGGY CODE ###

N, K = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
obj_list=[0,0]
for i, a in enumerate(p):
    if sum(obj_list)< sum(p[i:i+K]):
        obj_list = p[i:i+K]
ans = 0
for i in obj_list:
    a = sum(range(0,i+1,1))/i
    ans += a
print(ans)

### FIXED CODE ###

N, K = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
s = m = sum(p[:K])
for i in range(K,N):
    s += p[i]-p[i-K]
    m = max(m,s)
print((m+K)/2)
### BUGGY CODE ###

from collections import deque
from copy import copy
import bisect

n = int(input())
order = sorted(list(map(int, input().split())))
l = deque(order)
ans = 0

for _ in range(len(l)-2):
    first = l.pop()
    m = copy(l)
    for _ in range(len(m)-1):
        second = m.pop()
        fix = first-second
        ans += len(m)-bisect.bisect_right(list(m), fix)

print(ans)

### FIXED CODE ###

from bisect import bisect_right

n = int(input())
order = sorted(list(map(int, input().split())))
ans = 0

for i in reversed(range(2, n)):
    for j in reversed(range(1, i)):
        ans += j - bisect_right(order[0:j], order[i]-order[j])

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

from bisect import *
from collections import *
from fractions import gcd
from math import factorial
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
A=2*(10**6)+100
P=[0 for i in range(A+1)]

P[1]=1
for i in range(2,A):
    P[i]=P[i-1]*i%mod


def comb(x,y):
    if y>x or x<=0:
        return(0)
    elif y==0:
        return(1)
    else:
        return(P[x]*pow(P[x-y],mod-2,mod)%mod*pow(P[y],mod-2,mod)%mod)

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


### FIXED CODE ###

r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
A=2*(10**6)+3
P=[0 for i in range(A+1)]
P[1]=1
for i in range(2,A):
    P[i]=P[i-1]*i%mod

dr2=pow(P[r2],mod-2,mod)
dr1=pow(P[r1-1],mod-2,mod)
def combr2(x):
    y=r2
    if y>x or x<=0:
        return(0)
    elif y==0:
        return(1)
    else:
        return(P[x]*pow(P[x-y],mod-2,mod)%mod*dr2%mod)

def combr1(x):
    y=r1-1
    if y>x or x<=0:
        return(0)
    elif y==0:
        return(1)
    else:
        return(P[x]*pow(P[x-y],mod-2,mod)%mod*dr1%mod)
count=0
for i in range(c1+1,c2+2):
    count=(count+combr2(i+r2)-combr1(i+r1-1))%mod
print(count%mod)
### BUGGY CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
R = 10**9 + 7
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
s = inl()
t = inl()
dp = [ [0] * (m+1) for i in range(n) ]
dp[0][0] = 1 if s[0]==t[0] else 0
for i in range(1,n):
    dp[i][0] = dp[i-1][0] + (1 if s[i]==t[0] else 0)
for j in range(1,m):
    dp[0][j] = dp[0][j-1] + (1 if s[0]==t[j] else 0)

sh = defaultdict(list)
for i in range(1,n):
    sh[s[i]].append(i)

for j in range(1,m):
    for i in range(1,n):
        x = dp[i][j-1]
        for z in sh[t[j]]:  # s[z]==t[j]
          if z<=i:
            x = (x+dp[z-1][j-1]+1)%R  # z>0
        if t[j]==s[0]:
            x += 1
        dp[i][j] = x

if DBG:
    for i in range(n):
        print(dp[i])
print((dp[n-1][m-1]+1)%R)


### FIXED CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
R = 10**9 + 7
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
s = inl()
t = inl()
dp = [ [0] * (m+1) for i in range(n) ]
dp[0][0] = 1 if s[0]==t[0] else 0
for i in range(1,n):
    dp[i][0] = dp[i-1][0] + (1 if s[i]==t[0] else 0)
for j in range(1,m):
    dp[0][j] = dp[0][j-1] + (1 if s[0]==t[j] else 0)

sh = defaultdict(list)
for i in range(1,n):
    sh[s[i]].append(i)

for j in range(1,m):
    x = 0
    acc = [0] * (n+1)
    for z in sh[t[j]]:  # s[z]==t[j]
        x = (x+dp[z-1][j-1]+1)%R  # z>0
        acc[z] = x
    for i in range(1,n):
        acc[i] = (acc[i-1] if acc[i]==0 else acc[i])

    for i in range(1,n):
        x = dp[i][j-1]
        #for z in sh[t[j]]:  # s[z]==t[j]
        #  if z<=i:
        #    x = (x+dp[z-1][j-1]+1)%R  # z>0
        x += acc[i]
        if t[j]==s[0]:
            x += 1
        dp[i][j] = x%R

if DBG:
    for i in range(n):
        print(dp[i])
print((dp[n-1][m-1]+1)%R)
### BUGGY CODE ###

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

a = [0]
a.extend(list(map(int, input().split())))
step = 1
t = 0
if k<=5:
    for i in range(0, k):
        step = a[step]
    print(step)
else:

    for i in range(0, 4):
        step = a[step]

        step1 = step
    while(True):
        t += 1
        step1 = a[step1]
        if step1 == step:
            break
    result = step
    k = (k-4) % t
    for i in range(0, k):
        result = a[result]

    print(result)


### FIXED CODE ###

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

a = [0] + list(map(int, input().split()))
a1 = [0] * (n+1)

step = 1
start = 0
while(True):
    start += 1
    a1[step] += 1
    step = a[step]
    if a1[step] == 1:
        break
c = step
gap = 0
while(True):
    gap += 1
    step = a[step]
    if step == c:
        break
result = 1
if k > start:
    k = (k-start) % gap
    result = c
for _ in range(k):
    result = a[result]

print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    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()))

    ab = [aa + bb for aa in a for bb in b]
    ab.sort(reverse=True)
    ab = ab[:3000]

    abc = [aabb + cc for aabb in ab for cc in c]
    abc.sort(reverse=True)

    for i in range(k):
        print(abc[i])


main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    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()))

    ab = [aa + bb for aa in a for bb in b]
    ab.sort(reverse=True)
    ab = ab[:3000]

    abc = [aabb + cc for aabb in ab for cc in c]
    abc.sort(reverse=True)

    for i in range(k):
        print(abc[i])


main()
### BUGGY CODE ###

from collections import Counter
import math

def combinations_count(n):
    return (n * (n - 1)) // 2

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

dic = Counter(A)

for i in range(N):
    a = A[i]
    dic[a] -= 1
    ans = 0
    for v in dic.values():
        if v >= 2:
            ans += combinations_count(v)
    dic[a] += 1
    print(ans)


### FIXED CODE ###

from collections import Counter
import math

def combinations_count(n):
    return (n * (n - 1)) // 2

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

combs = {}
dic = Counter(A)
for k, v in dic.items():
    combs[k] = combinations_count(v)
ans = sum(combs.values())

for i in range(N):
    a = A[i]
    ans_i = ans
    if combs[a] < 2:
        ans_i -= combs[a]
        print(ans_i)
    else:
        ans_i -= dic[a] - 1
        print(ans_i)
### BUGGY CODE ###

n,m = map(int,input().split())
res = []
dic = {}
for i in range(m):
    p,y = map(int,input().split())
    res.append([p,y])
    if p not in dic:
        dic[p] = [y]
    else:
        dic[p].append(y)
        dic[p] = sorted(dic[p])        
for i in range(m):
    res[i][1] = dic[res[i][0]].index(res[i][1])+1
    print(str(res[i][0]).zfill(6)+str(res[i][1]).zfill(6))

### FIXED CODE ###

N,M = map(int,input().split())
PY = [[int(i) for i in input().split()]+[j] for j in range(M)]

dic = {}
PY.sort(key = lambda x:x[1])
ken = [0 for i in range(N)]
for k,value,s in PY:
    ken[k-1] += 1
    s1 = str(k).zfill(6)
    s2 = str(ken[k-1])
    s2 = s2.zfill(6)
    dic[s] = s1+s2

ans = sorted(dic.items(),key=lambda x:x[0])

for i,j in ans:
    print(j)
### BUGGY CODE ###

from bisect import bisect_left
n = int(input())
a = [int(input()) for _ in range(n)]

LIS = []  # LISの中身は、LISの最小の数字を保持する
LIS.append(a[0])
for i in range(1, n):
    idx = bisect_left(LIS, a[i])
    if idx == 0:
        LIS = [a[i]] + LIS
    else:
        LIS[idx-1] = a[i]
print(len(LIS))

### FIXED CODE ###

from bisect import bisect_left
from collections import deque
n = int(input())
a = [int(input()) for _ in range(n)]

LIS = deque()  # LISの中身は、LISの最小の数字を保持する
LIS.append(a[0])
for i in range(1, n):
    idx = bisect_left(LIS, a[i])
    if idx == 0:
        LIS.appendleft(a[i])
    else:
        LIS[idx-1] = a[i]
print(len(LIS))
### BUGGY CODE ###

import sys

input = sys.stdin.buffer.readline
r, c, k = map(int, input().split())


graph = [[0] * (c) for _ in range(r)]

for _ in range(k):
    d, e, f = map(int, input().split())
    graph[d - 1][e - 1] = f


# dijkstra
infi = 10 ** 10
money = [[[-infi] * (4) for _ in range(c)] for _ in range(r)]
money[0][0][0] = 0
for i in range(r):
    for j in range(c):
        for t in range(4):
            m = money[i][j][t]
            delta = graph[i][j]
            if i < r - 1:
                ni = i + 1
                nj = j
                nt = 0
                money[ni][nj][nt] = max(money[ni][nj][nt], m)
                if t < 3:
                    money[ni][nj][nt] = max(money[ni][nj][nt], m + delta)

            if j < c - 1:
                ni = i
                nj = j + 1
                nt = t
                money[ni][nj][nt] = max(money[ni][nj][nt], m)
                if t < 3:
                    nt = t + 1
                    money[ni][nj][nt] = max(money[ni][nj][nt], m + delta)


if graph[r - 1][c - 1] > 0:
    for t in range(3):
        money[r - 1][c - 1][t] += graph[r - 1][c - 1]
ans = max(money[r - 1][c - 1])

print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline
r, c, k = map(int, input().split())


graph = [[0] * (c) for _ in range(r)]

for _ in range(k):
    d, e, f = map(int, input().split())
    graph[d - 1][e - 1] = f


infi = 10 ** 10
money = [[[-infi] * (c) for _ in range(r)] for _ in range(4)]
money[0][0][0] = 0
for i in range(r):
    for j in range(c):
        for t in range(4):
            m = money[t][i][j]
            delta = graph[i][j]
            if i < r - 1:
                ni = i + 1
                nj = j
                nt = 0
                money[nt][ni][nj] = max(money[nt][ni][nj], m)
                if t < 3:
                    money[nt][ni][nj] = max(money[nt][ni][nj], m + delta)

            if j < c - 1:
                ni = i
                nj = j + 1
                nt = t
                money[nt][ni][nj] = max(money[nt][ni][nj], m)
                if t < 3:
                    nt = t + 1
                    money[nt][ni][nj] = max(money[nt][ni][nj], m + delta)

ans = 0
if graph[r - 1][c - 1] > 0:
    for t in range(3):
        money[t][r - 1][c - 1] += graph[r - 1][c - 1]
for i in range(4):
    ans = max(money[i][r - 1][c - 1], ans)

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

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

res=1
if M==N:
    for i in range(1, M+1):
        res*=i
    res=res*res*2
elif M-N==1:
    for i in range(1, N+1):
        res*=i
    res*=res*M
elif M-N==-1:
    for i in range(1, M+1):
        res*=i
    res*=res*N
else:
    res=0

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


### FIXED CODE ###

from math import *
M,N=input().split(' ')
M=int(M)
N=int(N)

res=1
if M==N:
    res=factorial(M)
    res=res*res*2
elif M-N==1:
    res=factorial(N)
    res*=res*M
elif M-N==-1:
    res=factorial(M)
    res*=res*N
else:
    res=0

print(res%(10**9+7))
### BUGGY CODE ###

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

	ans = 0

	import itertools

	for i in itertools.combinations(h,2):
		ans += (i[0]%(10**9 + 7)) * (i[1]%(10**9 + 7))
	print(ans%(10**9 + 7))
	

if __name__ == '__main__':
	main()

### FIXED CODE ###

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

	sum_h = sum(h)%(10**9 + 7)
	ans = 0
	for i in h:
		i = i%(10**9 + 7)
		sum_h -= i
		ans += i*sum_h

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

	

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

n=int(input())
v=list(map(int,input().split()))
c=list(map(int,input().split()))
sum=0
i=0
while i<n:
  if v[i]>c[i]:
    sum+=v[i]-c[i]
    i+=1
print(sum)


### FIXED CODE ###

n=int(input())
v=list(map(int,input().split()))
c=list(map(int,input().split()))
sum=0
i=0
while i<n:
    if v[i]>c[i]:
        sum+=v[i]-c[i]
    i+=1
print(sum)