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

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

A.sort()
B.sort()
C.sort()

import bisect
A2 = []
B2 = []
C2 = []
for a,b,c in zip(A,B,C):
    bisect.insort_left(A2, a)
    # bisect.insort_left(B2, b)
    bisect.insort_left(C2, c)
# print(A,B,C)
# import numpy as np

sum = 0
for b in B:
    sum += bisect.bisect_left(A, b) * (N - bisect.bisect_right(C, b))

# for c in C:
#     for b in [x for x in B if x < c]:
#         for a in [x for x in A if x < b]:

print(sum)

### FIXED CODE ###

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

A.sort()
B.sort()
C.sort()

import bisect
A2 = []
B2 = []
C2 = []
# for a,b,c in zip(A,B,C):
#     bisect.insort_left(A2, a)
#     # bisect.insort_left(B2, b)
#     bisect.insort_left(C2, c)
# print(A,B,C)
# import numpy as np

sum = 0
for b in B:
    sum += bisect.bisect_left(A, b) * (N - bisect.bisect_right(C, b))

# for c in C:
#     for b in [x for x in B if x < c]:
#         for a in [x for x in A if x < b]:

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

from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
	A[i], B[i], C[i] = map(int, input().split())

d = [[float("inf") for _ in range(N)] for _ in range(N)]

for i in range(M):
	d[A[i] - 1][B[i] - 1] = C[i]
	d[B[i] - 1][A[i] - 1] = C[i]

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]

p = permutations(r)
ans = float("inf")
for route in p:
	l = 0
	for i in range(R - 1):
		l += d[route[i] - 1][route[i + 1] - 1]

	if l < ans:
		ans = l

print(ans)

### FIXED CODE ###

from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
	A[i], B[i], C[i] = map(int, input().split())

d = [[float("inf") for _ in range(N)] for _ in range(N)]

for i in range(M):
	d[A[i] - 1][B[i] - 1] = C[i]
	d[B[i] - 1][A[i] - 1] = C[i]

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]
				d[j][i] = d[i][k] + d[k][j]

p = permutations(r)
ans = float("inf")
for route in p:
	l = 0
	for i in range(R - 1):
		l += d[route[i] - 1][route[i + 1] - 1]

	if l < ans:
		ans = l

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

N = int(input())
S = input()

tmp = [S[0], '']

for s in S[1:]:

    length = len(tmp)

    for i in range(length):
        if len(tmp[i]) < 26 and s not in tmp[i]:
            tmp.append(tmp[i]+s)

print((len(tmp)-1)%(10**9+7))

### FIXED CODE ###

from collections import Counter

N = int(input())
S = Counter(input())

ans = 1

for value in S.values():
    if value == 1:
        ans *= 2
    else:
        ans *= (value+1)
print((ans-1)%(10**9+7))
### BUGGY CODE ###

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

tree = {i:[] for i in range(1, n + 1)}
for _ in range(1, n):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

tmp = [1]
while len(tmp) != 0:
    tmp2 = tmp
    tmp = []
    for oya in tmp2:
        tmp.extend(tree[oya])
        for ko in tree[oya]:
            tree[ko].remove(oya)

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

ans = [0]*n
for p, x in cnt:
    tmp = [p]
    while len(tmp) != 0:
        for i in tmp:
            ans[i-1] += x
        tmp2 = tmp
        tmp = []
        for aaa in tmp2:
            tmp.extend(tree[aaa])

print(" ".join(map(str, ans)))

### FIXED CODE ###

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

tree = {i:[] for i in range(1, n + 1)}
for _ in range(1, n):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

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

check = [0]*n

tmp = [1]
while len(tmp) != 0:
    tmp2 = tmp
    tmp = []
    for oya in tmp2:
        check[int(oya)-1] = 1
        for ko in tree[oya]:
            if check[ko-1] == 0:
                cnt[ko-1] += cnt[oya-1]
                tmp.append(ko)


print(" ".join(map(str, cnt)))
### BUGGY CODE ###

def search(x,y,s1,s2,end1,end2):
  count = 0
  while  x < end1 and y < end2 and s1[x] == s2[y]:
    count += 1
    x += 1
    y += 1
  return count

def solve():
  while True:
    try:
      s1 = input()
      s2 = input()
      end1 = len(s1)
      end2 = len(s2)
      dic = dict()
      for i in range(end2):
        alp = s2[i]
        if not alp in dic:
          dic[alp] = [i]
        else:
          dic[alp].append(i)
      ans = 0
      for i in range(end1):
        alp = s1[i]
        if alp in dic:
          for ind in dic[alp]:
            a = search(i, ind, s1, s2, end1, end2)
            if ans < a:
              ans = a
      print(ans)
    except EOFError:
      break
solve()


### FIXED CODE ###

while True:
    try:
        s1 = input()
    except EOFError:
        break
    s2 = input()
    BASE = 27
    MOD = 1000000007


    def rolling_hash(s):
        h_lst = [0]
        for c in s:
            h_lst.append((h_lst[-1] * BASE + ord(c)) % MOD)
        return h_lst


    h_lst1 = rolling_hash(s1)
    h_lst2 = rolling_hash(s2)
    length1 = len(s1)
    length2 = len(s2)

    pow_mem = [pow(BASE, i, MOD) for i in range(min(length1, length2) + 1)]


    def check(center):
        hash_set = {(h_lst1[i + center] - h_lst1[i] * pow_mem[center]) % MOD for i in range(length1 - center + 1)}
        for i in range(length2 - center + 1):
            h2 = (h_lst2[i + center] - h_lst2[i] * pow_mem[center]) % MOD
            if h2 in hash_set:return True
        return False


    left = 0
    right = min(length1, length2)
    while right > left + 1:
        center = (left + right) // 2
        if check(center):
            left = center
        else:
            right = center
    print(right if check(right) else left)
### BUGGY CODE ###

import numpy as np
n=int(input())
dam=[int(x)*2 for x in input().split()]
a=[[0]*n for x in range(n)]
for i in range(n):
    a[i][i],a[i][(i+1)%n]=1,1
a=np.array(a)
dam=np.array(dam)
ans=np.linalg.solve(a,dam)
print(" ".join([str(int(ans[i])) for i in range(n)]))

### FIXED CODE ###

n=int(input())
dam=[int(x) for x in input().split()]
yama=[0]*n
dam_sum=sum(dam)//2
diff=0
if n in (1,2):
    for j in range(n):
        diff=0
        for i in range(n):
            if i%2==0:
                continue
            diff+=dam[(i+j)%n]
        yama[j]=dam_sum - diff
        yama[j]*=2
else:
    diff_same=0
    for i in range(n):
            if i%2==0:
                continue
            diff_same+=dam[(i)%n]
    yama[0]=dam_sum - diff_same
    yama[0]*=2
    diff_odd=0
    for i in range(n):
            if i%2==0:
                continue
            diff_odd+=dam[(i+1)%n]
    yama[1]=dam_sum - diff_odd
    yama[1]*=2
    for j in range(2,n):
        if j%2==0:
            diff_same-=dam[(j-1)%n]
            diff_same+=dam[(j-2)%n]
            yama[j]=dam_sum - diff_same
        else:
            diff_odd-=dam[(j-1)%n]
            diff_odd+=dam[(j-2)%n]
            yama[j]=dam_sum - diff_odd
        yama[j]*=2
print(" ".join([str(x) for x in yama]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

rem=k
nxt=1
visit=[]
for i in range(k):
    visit.append(nxt)
    nxt=a[nxt-1]
    if nxt in visit:
        break
    rem-=1

if rem==0:
    print(nxt)
else:
#    print('-'*60)
#    print('nxt=', nxt)
#    print('rem=', rem)
#    print('visit=', visit)
    
    loops=visit[visit.index(nxt):]
    print(loops[(rem-1)%len(loops)])    
    
#    print('-'*60)
#    print('loops=', loops)

### FIXED CODE ###

# -*- coding: utf-8 -*-
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

rem=k
nxt=1
visit=[]
visit_set=set([])
for i in range(k):
    visit.append(nxt)
    visit_set.add(nxt)
    nxt=a[nxt-1]
    # この判定をやめる
    if nxt in visit_set:
        break
    rem-=1

if rem==0:
    print(nxt)
else:
#    print('-'*60)
#    print('nxt=', nxt)
#    print('rem=', rem)
#    print('visit=', visit)
    
    loops=visit[visit.index(nxt):]
    print(loops[(rem-1)%len(loops)])    
    
#    print('-'*60)
#    print('loops=', loops)
### BUGGY CODE ###

import bisect
from collections import deque
n, m = map(int, input().split())
A = deque(sorted(map(int, input().split())))
BC = []
for j in range(m):
    b, c = map(int, input().split())
    BC.append((b, c))
BC = sorted(BC, key=lambda x: x[1], reverse=True)
for b, c in BC:
    i = bisect.bisect_left(A, c)
    if i == 0:
        break
    else:
        start = min(i, b)
        for _ in range(start):
            A.popleft()
            A.append(c)
print(sum(A))

### FIXED CODE ###

n, m = map(int, input().split())
A = sorted(map(int, input().split()))
BC = []
for j in range(m):
    b, c = map(int, input().split())
    BC.append((b, c))
BC = sorted(BC, key=lambda x: x[1], reverse=True)
D = []
for b, c in BC:
    D.extend([c for i in range(b)])
    if len(D) >= n:
        D = D[:n]
        break
for x in range(len(D)):
    if A[x] > D[x]:
        break
else:
    x += 1
print(sum(A[x:]) + sum(D[:x]))
### BUGGY CODE ###


import sys
import queue
sys.setrecursionlimit(10**7)


def inpl():
    return list(map(int, input().split()))


N, M = inpl()

lines = [[] for _ in range(N)]
for _ in range(M):
    a, b = inpl()
    a -= 1
    b -= 1
    lines[a].append(b)
    lines[b].append(a)


ans = [-1] * N


q = queue.Queue()
q.put((0, 0))
while not q.empty():
    s, b = q.get()

    if ans[s] != -1:
        continue
    else:
        ans[s] = b
        for t in lines[s]:
            q.put((t, s))


print("Yes")
for a in ans[1:]:
    print(a + 1)


### FIXED CODE ###


import sys
import queue
sys.setrecursionlimit(10**7)


def inpl():
    return list(map(int, input().split()))


N, M = inpl()

lines = [[] for _ in range(N)]
for _ in range(M):
    a, b = inpl()
    a -= 1
    b -= 1
    lines[a].append(b)
    lines[b].append(a)


ans = [-1] * N


q = queue.Queue()
q.put((0, 0))
while not q.empty():
    s, b = q.get()

    if ans[s] != -1:
        continue
    else:
        ans[s] = b
        for t in lines[s]:
            q.put((t, s))


print("Yes")
for a in ans[1:]:
    print(a + 1)
### BUGGY CODE ###

# Prime Number

import sys


count = 0
primes = [2, 3]

for n in xrange(5, 1000001, 2):
	isprime = True
	for i in xrange(1, len(primes)):
		count += 1
		if primes[i] * primes[i] > n:
			break
		count += 1
		if n % primes[i] == 0:
			isprime = False
			break
	if isprime:
		primes.append(n)

datas = []

for line in sys.stdin:
	datas.append(int(line))

for data in datas:
	count = 0
	for prime in primes:
		if prime <= data:
			count += 1
		else:
			break
	print count

### FIXED CODE ###

# Prime Number

import sys


MAX_NUM = 1000000
ROOT_MAX_NUM = 1000

primes = [1] * MAX_NUM

primes[0] = primes[1] = 0

for i in xrange(2, ROOT_MAX_NUM):
	if not primes[i]:
		continue
	for j in xrange(i+i, MAX_NUM, i):
		primes[j] = 0

datas = []

for line in sys.stdin:
	datas.append(int(line))

for data in datas:
	count = 0
	for i in xrange(data+1):
		if primes[i]:
			count += 1
	print count
### BUGGY CODE ###

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

A.sort()
for _ in range(m):
    A[-1] /= 2
    A.sort()
A = [int(a) for a in A]

print(sum(A))


### FIXED CODE ###

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

A = [a * (-1) for a in A]
import heapq
heapq.heapify(A)

for _ in range(m):
    a = heapq.heappop(A) * (-1)
    heapq.heappush(A, a // 2 * (-1))

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

n,q = map(int,input().split())
s = input()
lr = []
for i in range(0,q):
    lr.append(input().split())
map(int,lr)

lrCut = []
for i in range(0,q):
    lrCut.append(s[int(lr[i][0]) - 1:int(lr[i][1])])

for i in range(0,q):
    lrCut[i] = lrCut[i].replace("AC","Q")
    sum = 0
    for j in lrCut[i]:
        if j == "Q":
            sum += 1
    print(sum)


### FIXED CODE ###

# -*- coding: utf-8 -*-

n, q = map(int,input().split())
s = list(input())
l = [0] * q
r = [0] * q
for i in range(q):
    l[i],r[i] = map(int,input().split())

aclist = []

cnt = 0
for i in range(n):
    if s[i-1] == "A" and s[i] == "C":
        cnt += 1
        aclist.append(cnt)
    else:
        aclist.append(cnt)

for i in range(q):
    print(aclist[r[i]-1] - aclist[l[i]-1])
### BUGGY CODE ###

import numpy as np
import collections
import math

s = input()[::-1]
length = len(s)
a = np.zeros(length, dtype=int)
d = np.zeros(length, dtype=int)

for i in range(length):
    a[i] = int(s[i]) * pow(10, i) % 2019
d[0] = a[0]

for i in range(length-1):
    d[i+1] = (d[i] + a[i+1]) % 2019
    
x = np.array([i for i in collections.Counter(d).values()])
x = x[np.where(x > 1)]

print(int(sum([math.factorial(x[i]) for i in range(x.shape[0])]) / 2) + d.shape[0] - np.count_nonzero(d))

### FIXED CODE ###

import numpy as np

s = input()[::-1]
length = len(s)
a = np.zeros(length, dtype=int)
d = np.zeros(length, dtype=int)
ans = np.zeros(2019, dtype=int)
x = 10

a[0] = int(s[0])
d[0] = a[0]
ans[d[0]] += 1

for i in range(1, length):
    a[i] = int(s[i]) * x % 2019
    d[i] = (d[i-1] + a[i]) % 2019
    ans[d[i]] += 1
    x = x * 10 % 2019

ans_c = ans[np.nonzero(ans)]

print(int(sum([ans_c[i] * (ans_c[i]-1) for i in range(ans_c.shape[0])]) / 2) + ans[0])
### BUGGY CODE ###

import itertools
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a_tmp = [0] + list(itertools.accumulate(a))
b_tmp = [0] + list(itertools.accumulate(b))
ans = 0

for i in range(n+1):
    for j in range(m+1):
        if a_tmp[i]+b_tmp[j] <= k:
            ans = max(ans, i+j)
print(ans)


### FIXED CODE ###

import itertools
import bisect
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a_acc = [0] + list(itertools.accumulate(a))
b_acc = [0] + list(itertools.accumulate(b))
ans = 0

for i in range(n+1):
    if k - a_acc[i] >= 0:
        ans = max(ans, i + bisect.bisect(b_acc, k - a_acc[i])-1)
print(ans)
### BUGGY CODE ###

from math import gcd

N = int(input())
A = list([int(x) for x in input().split()])

before = 0
result = [0] * (max(A) + 1)

for i in A:
    before = gcd(before, i)
    result[i] += 1

is_pairwise = True
for i in range(2, max(A) + 1):
    cnt = 0
    for j in range(i, max(A) + 1, i):
        cnt += result[j]

    if cnt > 1:
        is_pairwise = False
        break

if is_pairwise:
    print('pairwise coprime')
    exit()

if before == 1:
    print('setwise coprime')
else:
    print('not coprime')


### FIXED CODE ###

from math import gcd


def main():
    N = int(input())
    A = list([int(x) for x in input().split()])

    max_a = max(A)

    before = 0
    result = [0 for _ in range(max_a + 1)]

    for i in A:
        before = gcd(before, i)
        result[i] += 1

    is_pairwise = True
    for i in range(2, max_a + 1):
        cnt = 0
        for j in range(i, max_a + 1, i):
            cnt += result[j]

        if cnt > 1:
            is_pairwise = False
            break

    if is_pairwise:
        print('pairwise coprime')
        exit()

    if before == 1:
        print('setwise coprime')
    else:
        print('not coprime')


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

k=int(input())
n=len(input())
mod=10**9+7

def prepare(m, mod=10 ** 9 + 7):
	fac = [1] * (m + 1)
	inv = [1] * (m + 1)
	for i in range(1, m + 1):
		fac[i] = fac[i - 1] * i % mod
	inv[-1] = pow(fac[-1], mod - 2, mod)
	for i in range(m - 1, -1, -1):
		inv[i] = inv[i + 1] * (i + 1) % mod
	return fac, inv

fac, inv = prepare(n+k)

def cmb(n, r):
	assert n >= r >= 0
	return fac[n] * inv[n - r] * inv[r] % mod

ans=0
for i in range(0,k+1):
	ans+=pow(25,k-i,mod)*pow(26,i,mod)%mod*cmb(n+k-i-1,k-i)%mod
	ans%=mod
print(ans)

### FIXED CODE ###

k=int(input())
n=len(input())
mod=10**9+7

def prepare(m, mod=10 ** 9 + 7):
	fac = [1] * (m + 1)
	inv = [1] * (m + 1)
	for i in range(1, m + 1):
		fac[i] = fac[i - 1] * i % mod
	inv[-1] = pow(fac[-1], mod - 2, mod)
	for i in range(m - 1, -1, -1):
		inv[i] = inv[i + 1] * (i + 1) % mod
	return fac, inv

fac, inv = prepare(n+k)

def cmb(n, r):
	assert n >= r >= 0
	return fac[n] * inv[n - r] * inv[r] % mod

ans=0
for i in range(0,k+1):
	ans+=pow(25,k-i,mod)*pow(26,i,mod)%mod*cmb(n+k-i-1,k-i)%mod
	ans%=mod
print(ans)
### BUGGY CODE ###

'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    q = int(ipt())
    for _ in range(q):
        a,b = map(int,ipt().split())
        if a > b:
            a,b = b,a
        ans = a-1
        tgt = a*b
        pi = b
        for i in range(a+1,10**9+1):
            xi = (tgt-1)//i
            if xi == pi:
                ans += xi-1
                break
            ans += 1
            pi = xi
        print(ans)

    return None

if __name__ == '__main__':
    main()


### FIXED CODE ###

'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    q = int(ipt())
    for _ in range(q):
        a,b = map(int,ipt().split())
        if a > b:
            a,b = b,a
        tgt = a*b
        rt = int(tgt**0.5+0.0000000000001)
        ans = rt*2-1
        if a == b:
            ans -= 1
        elif rt**2 == tgt:
            ans -= 2
        elif rt*(rt+1) < tgt:
            pass
        elif rt**2-1 < tgt:
            ans -= 1
        print(ans)

    return None

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

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n = iinput()
a = iarr()
amax = 10**6

# ふるって生き残ったやつがTrue
dp = [1 for i in range(amax+1)]
for num in a:
    for i in range(2, amax//num + 1): dp[num * i] = 0

# カウンター
cnt = col.Counter(a)

# 生き残っていて、かつ、１回だけ登場するやつ
ans = 0
for key,val in cnt.items():
    if dp[key] and val==1: ans += 1

print(ans)


### FIXED CODE ###

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n = iinput()
a = iarr()
amax = max(a)
#amax = 10**6

cnt = [0 for i in range(amax+1)]
for num in a:
    for i in range(1,amax//num + 1):
        tmp = num * i
        cnt[tmp] += 1

ans = 0
for num in a:
    if cnt[num]==1: ans += 1
print(ans)
### BUGGY CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]
s = 0
for j in range(1, n):
    for i in range(0, j):
        if a[i] >= 10**9 +7:
            a[i] -= (10**9 +7)
        if a[j] >= 10**9 +7:
            a[j] -= (10**9 +7)
        if a[i] * a[j] >= 10**9 +7:
            s += a[i] * a[j] % (10**9 + 7)
        else:
            s += a[i] * a[j]
        if s >= 10**9 +7:
            s = s % (10**9 + 7)
print(s)

### FIXED CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]
s = 0
t = 0
b = 0
m = 10 ** 9 + 7
for i in range(n):
    t += a[i]
    t = t % m
    b += a[i] ** 2
    b = b % m
s += int(((((t ** 2) % m + m - b) % m) * (5 * 10 ** 8 + 4)) % m)
print(s)
### BUGGY CODE ###

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

#check max

MX = [sum(Pi[i:i+K]) for i in range(N-K+1)]

m= max(MX)
ans= (1/2)*(m + K)
print(ans)


### FIXED CODE ###

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

Sim = [0]
for i in range(0,N):
  Sim.append(Sim[i]+Pi[i])
MAX = max(Sim[i+K] - Sim[i] for i in range(N+1-K))

print((MAX+K)/2)
### BUGGY CODE ###

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

c.sort()

### 二分探索
ans = 0
for i in range(n):
    for j in range(n):
        if a[i] < b[j]:
            for k in range(len(c)):
                low = 0
                high = len(c) - 1
                item = c[k]

                while low <= high:
                    mid = (low + high) //2
                    guess = c[mid]
                    if guess == item:
                        break
                    if guess > item:
                        high = mid -1
                    else:
                        low = mid + 1

                if c[mid] > b[j]:
                    ans += 1
print(ans)

### FIXED CODE ###

import bisect

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
 
A.sort()
C.sort()
 
ans = 0
for i in range(N):
    a = bisect.bisect_left(A, B[i])
    c = bisect.bisect_right(C, B[i])
    ans += a*(N-c)
print(ans)
### BUGGY CODE ###

N, M = map( int, input().split() )
a = list( map( int, input().split() ) )
 
for i in range( M ):
  b, c = map( int, input().split() )
  a += [ c ] * b
 
a.sort()
print(sum(a[-N:]))

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1])
for b,c in bc[::-1]:
  a.extend([c]*b)
  if len(a)>2*n:
    break
a.sort(reverse=True)
print(sum(a[:n]))