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

def binary_search_A(N,A,b):
    upper = N - 1
    lower = 0
    
    while upper - lower > 1:
        middle = upper + lower // 2
        if A[middle] > b:
            upper = middle
        else:
            lower = middle
            
    if b >= A[upper]:
      return upper+1
    elif b >= A[lower]:
      return lower+1
    else:
      return lower

def binary_search_C(N,C,b):
    upper = N - 1
    lower = 0
    
    
    while upper - lower > 1:
        middle = upper + lower // 2
        if C[middle] > b:
            upper = middle
        else:
            lower = middle
            
            
    if b < C[lower]:
      return N-lower
    elif b < C[upper]:
      return N - (lower+1)
    else:
      return N - (upper+1)
    


N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
A.sort()
B.sort()
C.sort()

ans = 0

for i in range(N):
    j = binary_search_A(N, A, B[i])
    #print(j)
    k = binary_search_C(N, C, B[i])
    #print(k)
    ans += j * k
    
print(ans)

### FIXED CODE ###

def binary_search_low(ls, v):
    """
    [input]
        ls: 二分探索するリスト(配列)
        v: 探索の基準となる値
    [output]
        ok: 基準を満たす最大index
        (ng: 基準を満たさない最小index)
    """
    ok = -1
    ng = n

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if ls[mid] < v: ok = mid
        else: ng = mid
        
    return ok  #, ng
    
def binary_search_high(ls, v):
    """
    [input]
        ls: 二分探索するリスト(配列)
        v: 探索の基準となる値
    [output]
        ok: 基準を満たす最大index
        (ng: 基準を満たさない最小index)
    """
    ng = -1
    ok = n

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if ls[mid] > v: ok = mid
        else: ng = mid
        
    return ok


n = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
ans = 0
for b in B:
    a_count = binary_search_low(A,b) + 1
    b_count = n - binary_search_high(C, b)
    #print(a_count,b_count)

    ans += a_count*b_count


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

N = int(input())
print(sum(i+1 for i in range(N-1)))

### FIXED CODE ###

import numpy as np
N = int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

H, W = map(int, input().split())

def bfs(h, w):
    ls = deque([[h, w, 0]])
    direction = [[1,0], [-1,0], [0,1], [0,-1]]
    while len(ls) > 0:
        h, w, depth = ls.popleft()
        
        for dh, dw in direction:
            if h + dh < 0 or H-1 < h + dh: continue
            if w + dw < 0 or W-1 < w + dw: continue
            if depth + 1 < D[h+dh][w+dw] and G[h+dh][w+dw] != "#":
                ls.append([h+dh, w+dw, depth+1])
                D[h+dh][w+dw] = depth + 1

G = [[i for i in input()] for j in range(H)]
D = [[float("inf")] * W for i in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            bfs(h, w)
            
ans = 0
for h in range(H):
    for w in range(W):
        if D[h][w] == float("inf"):
            continue
        ans = max(ans, D[h][w])
        
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
G = [[i for i in input()] for j in range(H)]

ls = []
dp = [[-1 for i in range(W)] for j in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            ls.append([h,w])
            dp[h][w] = 1

ans = -1
while len(ls) > 0:
    ans += 1
    temp = []
    for h, w in ls:
        if 0 <= h+1 <= H-1 and dp[h+1][w] == -1:
            dp[h+1][w] = 1
            temp.append([h+1,w])
        if 0 <= h-1 <= H-1 and dp[h-1][w] == -1:
            dp[h-1][w] = 1
            temp.append([h-1,w])
        if 0 <= w+1 <= W-1 and dp[h][w+1] == -1:
            dp[h][w+1] = 1
            temp.append([h,w+1])
        if 0 <= w-1 <= W-1 and dp[h][w-1] == -1:
            dp[h][w-1] = 1
            temp.append([h,w-1])
    ls = temp

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

n, m = map(int, input().split())
a = [int(_) for _ in input().split()]
a.sort(reverse=True)

ans = 0
search_idx = 0

for i in range(m):
    max_idx = 0
    if search_idx+2 >= n:
        search_idx = n - 2
    for j in range(0, search_idx+2):
        if a[max_idx] < a[j]:
            max_idx = j
        if search_idx < max_idx:
            search_idx = max_idx
    a[max_idx] //= 2
    #print(a)

print(sum(a))

### FIXED CODE ###

import heapq

# 「優先度付きキュー」の練習問題

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

# 各要素を-1倍する。最大値の取り出しができるように
a = list(map(lambda x: x*(-1), a))
# aの優先度付きキューに
heapq.heapify(a)

# 割引m回分ループ
for _ in range(m):
    popNum = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-popNum//2))

# 負で出力されているので戻す
print(-sum(a))
### BUGGY CODE ###

a,b = map(int,input().split())	
ko=[]
for i in range(min(a,b)):
    i+=1
    if(a%i==0 and b%i==0):
        ko+=[i]
for i in range(len(ko)):
    for j in range(ko[i]//2):
        j+=2
        if ko[i]!=2 and ko[i]%j==0:
            ko[i]=0
            break
ans=0
for i in range(len(ko)):
    if ko[i]!=0:
        ans+=1
print(ans)

### FIXED CODE ###

def yakusu(x):
    ans=[1]
    check=2
    while(x!=1 and check <= int(x**0.5)+2):
        if(x%check==0):
            ans.append(check)
            while(x%check==0):
                x=x//check
        check+=1
    if x != 1:
      ans.append(x)
    return ans
def main():
    a,b = map(int,input().split())	
    ans=0
    y1=yakusu(a)
    for i in y1:
        if b%i==0:
            ans+=1
    print(ans)
 
main()
### BUGGY CODE ###

# coding: utf-8
N = int(input())
S = 'D' + input()


rgb_count = [[0 for i in range(3)] for j in range(N+1)]
for i in range(1, N+1):
    if S[i] == 'R':
        rgb_count[1][0] += 1
    elif S[i] == 'G':
        rgb_count[1][1] += 1
    else:
        rgb_count[1][2] += 1


dict={'R':0, 'G':1, 'B':2}
d = ['', 'B', 'G', 'R']
dic = {'R': [1,2], 'G': [0,2], 'B': [0,1]}
ret = rgb_count[1][0]*rgb_count[1][1]*rgb_count[1][2]
for i in range(2,N):
    ran = min([i-1, N-i])
    if ran < 1: continue
    for k in range(1, ran+1):
        if set([S[i-k], S[i], S[i+k]]) == set(['G', 'B', 'R']):
            ret -= 1

print(ret)

### FIXED CODE ###

# coding: utf-8
N = int(input())
S = 'D' + input()


rgb_count = [[0 for i in range(3)] for j in range(N+1)]
for i in range(1, N+1):
    if S[i] == 'R':
        rgb_count[1][0] += 1
    elif S[i] == 'G':
        rgb_count[1][1] += 1
    else:
        rgb_count[1][2] += 1


dict={'R':1, 'G':2, 'B':4}
d = ['', 'B', 'G', 'R']
dic = {'R': [1,2], 'G': [0,2], 'B': [0,1]}
ret = rgb_count[1][0]*rgb_count[1][1]*rgb_count[1][2]
for i in range(2,N):
    ran = min([i-1, N-i])
    if ran < 1: continue
    for k in range(1, ran+1):
        if dict[S[i-k]]+dict[S[i]]+dict[S[i+k]] == 7:
            ret -= 1

print(ret)
### BUGGY CODE ###

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

facs = [1] * (n+k)
invs = [1] * (n+k)
nfac = 1
for i in range(1, n+k):
    nfac = nfac * i % mod
    facs[i] = nfac
    invs[i] = pow(facs[i], mod-2, mod)

ans = 0
for i in range(k+1):
    left = facs[i+n-1] * invs[i] * invs[n-1] % mod
    left = left * pow(25, i, mod) % mod
    ans += left * pow(26, k-i, mod) % mod
    ans %= mod
print(ans)

### FIXED CODE ###

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

facs = [1] * (n+k)
# invs = [1] * (n+k)
nfac = 1
for i in range(1, n+k):
    nfac = nfac * i % mod
    facs[i] = nfac
    # invs[i] = pow(facs[i], mod-2, mod)
invn1 = pow(facs[n-1], mod-2, mod)

ans = 0
for i in range(k+1):
    left = facs[i+n-1] * pow(facs[i], mod-2, mod) * invn1 % mod
    left = left * pow(25, i, mod) % mod
    ans += left * pow(26, k-i, mod) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
S = list(str(input()))
S.reverse()
extra = 0
each_extras = [[0 for i in range(10)] for i in range(S.count("?"))]
cnt = 0
for i in range(len(S)):
    if S[i] != "?":
        extra += int(S[i]) * 10 ** i
    else:
        each_extras[cnt] = [0 for i in range(13)]
        for x in range(10):
            each_extras[cnt][x * 10 ** i % 13] = 1
        cnt += 1

# print(extra)
dp = [[0 for i in range(13)] for j in range(cnt+1)]
dp[0][extra % 13] = 1
for i in range(cnt):
    for j in range(13):
        for e_i in range(13):
            if each_extras[i][e_i]:
                dp[i+1][(j+e_i) % 13] += dp[i][j]
    for j in range(13):
        dp[i+1][j] = dp[i+1][j] % mod

# print(dp)
print(dp[-1][5] % mod)


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))


"""
S.reverse()
extra = 0
each_extras = [[0 for i in range(10)] for i in range(S.count("?"))]
cnt = 0
for i in range(len(S)):
    if S[i] != "?":
        extra += int(S[i]) * 10 ** i
    else:
        each_extras[cnt] = []
        for x in range(10):
            each_extras[cnt].append(x * 10 ** i % 13)
            # each_extras[cnt][x * 10 ** i % 13] = 1
        cnt += 1

# print(each_extras)

# print(extra)
dp = [[0 for i in range(13)] for j in range(cnt+1)]
dp[0][extra % 13] = 1
for i in range(cnt):
    for extras in each_extras[i]:
        for j in range(13):
            dp[i+1][(extras + j)%13] += dp[i][j]
            dp[i+1][(extras + j)%13] %= mod
    for j in range(13):
        dp[i+1][j] = dp[i+1][j] % mod


# print(dp)
print(dp[-1][5] % mod)
"""


S = list(str(input()))

dp = [[0 for i in range(13)]for j in range(len(S)+1)]
dp[0][0] = 1
S.reverse()
mul = 1
for i in range(len(S)):
    if S[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(mul*j+k)%13] += dp[i][k]
                dp[i+1][(mul*j+k)%13] %= mod
    else:
        for k in range(13):
            dp[i+1][(int(S[i])*mul+k)%13] += dp[i][k]
            dp[i+1][(int(S[i])*mul+k)%13] %= mod
    mul *= 10
    mul %= 13

# print(dp)
print(dp[-1][5])
### BUGGY CODE ###

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

import math
from functools import reduce

def gcd_list(numbers):
  return reduce(math.gcd, numbers)

def sieve_of_eratosthenes(n): 
    candidate = [i for i in range(2, n+1)] 
    prime = []
    limit = math.sqrt(n) + 1 

    while True:
        p = min(candidate) 
        if limit <= p:
            prime.extend(candidate) 
            break
        prime.append(p) 

        candidate = [i for i in candidate if i % p != 0]

    return prime

prime = sieve_of_eratosthenes(10**6+1)

for p in prime:
  cnt = 0
  for a in A:
    if a%p == 0: cnt += 1
    if cnt == 2:
      if gcd_list(A) == 1: print('setwise coprime')
      else: print('not coprime')
      exit()
print('pairwise coprime')


### FIXED CODE ###

import math
from functools import reduce

def gcd_list(numbers):
  return reduce(math.gcd, numbers)

N=int(input())
A=list(map(int,input().split()))
mA = max(A)
D = [-1]*(mA+1)
D[0]=1
D[1]=1
for i in range(2,mA+1):
  if D[i] != -1: continue
  D[i] = i
  cnt = 2*i
  while cnt < mA+1:
    if D[cnt] == -1:
      D[cnt]=i
    cnt += i
done = set()
for a in A:
  tmp = set()
  while a > 1:
    tmp.add(D[a])
    a //= D[a]
  if len(done&tmp) > 0:
    if gcd_list(A) == 1: print('setwise coprime')
    else: print('not coprime')
    exit()
  done |= tmp
print('pairwise coprime')
### BUGGY CODE ###

def main():
    N = int(input())
    L = list(map(int, input().split()))
    sort_L = sorted(L)
    cnt = 0
    for i in range(N):
        for j in range(i+1,N):
            if i == j:
                continue
            for k in range(max(i,j)+1,N):
                if sort_L[i] + sort_L[j] > sort_L[k]:
                    cnt += 1
                else:
                    break

    print(cnt)

    

if __name__ == "__main__":
    main()

### FIXED CODE ###

import bisect

def main():
    N = int(input())
    L = list(map(int, input().split()))
    sort_L = sorted(L)
    cnt = 0
    for i in range(N-2):
        for j in range(i+1,N-1):
            tmp = bisect.bisect_left(sort_L,sort_L[i] + sort_L[j])
            if tmp - 1 > j:
                cnt += tmp - j - 1
    print(cnt)

    

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

from collections import deque

H, W = map(int, input().split())
field = tuple([input() for _ in range(H)])

#右上左下
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]


#(sy, sx)に一番近いところを探す
def bsf(sy, sx):

    if field[sy][sx] == "#":
        return 0
    
    else:
        dist = [[-1 for x in range(W)] for y in range(H)]
        que = deque()
        que.append((sy, sx))
        dist[sy][sx] = 0

        while len(que):
            n = que.popleft()
            ny = n[0]
            nx = n[1]

            for i in range(4):
                nny = ny + dy[i]
                nnx = nx + dx[i]

                if nny < 0 or nny >= H or nnx < 0 or nnx >= W:
                    continue

                elif field[nny][nnx] == "." and dist[nny][nnx] == -1:
                    dist[nny][nnx] = dist[ny][nx] + 1
                    que.append((nny, nnx))

                elif field[nny][nnx] == "#":
                    return dist[ny][nx] + 1

l = []

for i in range(H):
    for j in range(W):
        l.append(bsf(i, j))

print(max(l))

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]

#右上左下
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]


ans = 0

que = deque()

num_white = H * W

paint = 0

for i in range(H):
    for j in range(W):
        if field[i][j] == "#":
            que.append((i, j))
            num_white -= 1

def check(field):
    flag = False
    for i in range(H):
        if "." in field[i]:
            flag = True

    return flag

def one_bsf():
    global paint
    global que
    global ans

    for _ in range(len(que)):
        n = que.popleft()
        ny = n[0]
        nx = n[1]

        for i in range(4):
            nny = ny + dy[i]
            nnx = nx + dx[i]

            if nny < 0 or nny >= H or nnx < 0 or nnx >= W:
                continue

            elif field[nny][nnx] == ".":
                field[nny][nnx] = "#"
                paint += 1
                que.append((nny, nnx))

    ans += 1

while num_white != paint:
    one_bsf()
    
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
l,n=map(int,input().split())
c=n
tree1=[int(i) for i in sys.stdin]
reversed_tree1=[l-i for i in reversed(tree1)]
tree=deque(tree1)
reversed_tree=deque(reversed_tree1)
if n%2 == 0:
  ans= sum(tree1)*2 + l*(n-1) +tree1[n//2] - sum(tree1[n//2:])*4
  ans2= sum(reversed_tree1)*2 + l*(n-1) +reversed_tree1[n//2] - sum(reversed_tree1[n//2:])*4
  n-=1
  c-=1
  ans3= ans-tree.popleft()*2-l+tree[n//2]*2
  ans= max(ans,ans3)
  ans4= ans2-reversed_tree.popleft()*2-l+(reversed_tree[n//2])*2
  ans2= max(ans2,ans4)
else:
  ans= sum(tree1)*2 + l*(n-1) - tree1[n//2] - sum(tree1[((n//2)+1):])*4
  ans3=ans
  ans2= sum(reversed_tree1)*2 + l*(n-1) - reversed_tree1[n//2] - sum(reversed_tree1[((n//2)+1):])*4
  ans4=ans2
for i in range(n//2):
  n-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[(n-1)//2]+tree[(n+1)//2]
  ans= max(ans_stack,ans)
  ans3=ans_stack
  n-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[n//2]*2
  ans=max(ans_stack,ans)
  ans3=ans_stack
n=c
for i in range(n//2):
  n-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[(n-1)//2]+reversed_tree[(n+1)//2]
  ans2=max(ans_stack,ans2)
  ans4=ans_stack
  n-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[n//2]*2
  ans2=max(ans2,ans_stack)
  ans4=ans_stack
print(max(ans,ans2))


### FIXED CODE ###

import sys
from collections import deque
l,n=map(int,input().split())
c=n
tree1=[int(i) for i in sys.stdin]
reversed_tree1=[l-i for i in reversed(tree1)]
tree=deque(tree1)
reversed_tree=deque(reversed_tree1)
if n%2 == 0:
  ans= sum(tree1)*2 + l*(n-1) +tree1[n//2] - sum(tree1[n//2:])*4
  ans2= sum(reversed_tree1)*2 + l*(n-1) +reversed_tree1[n//2] - sum(reversed_tree1[n//2:])*4
  n-=1
  c-=1
  ans3= ans-tree.popleft()*2-l+tree[n//2]*2
  ans= max(ans,ans3)
  ans4= ans2-reversed_tree.popleft()*2-l+(reversed_tree[n//2])*2
  ans2= max(ans2,ans4)
else:
  ans= sum(tree1)*2 + l*(n-1) - tree1[n//2] - sum(tree1[((n//2)+1):])*4
  ans3=ans
  ans2= sum(reversed_tree1)*2 + l*(n-1) - reversed_tree1[n//2] - sum(reversed_tree1[((n//2)+1):])*4
  ans4=ans2
for i in range(n//2):
  n-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[(n-1)//2]+tree[(n+1)//2]
  ans= max(ans_stack,ans)
  ans3=ans_stack
  n-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[n//2]*2
  ans=max(ans_stack,ans)
  ans3=ans_stack
n=c
for i in range(n//2):
  n-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[(n-1)//2]+reversed_tree[(n+1)//2]
  ans2=max(ans_stack,ans2)
  ans4=ans_stack
  n-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[n//2]*2
  ans2=max(ans2,ans_stack)
  ans4=ans_stack
print(max(ans,ans2))
### BUGGY CODE ###

candidates = [2] + list(range(3,100001,2))
i = 1
got_one = True
while got_one:
    p = candidates[i]
    new_candidates = candidates[:i+1]
    for j in candidates[i+1:]:
        if j%p != 0:
            new_candidates.append(j)
    if len(new_candidates) == len(candidates):
        got_one = False
    candidates = new_candidates
    i = i + 1

similar = []
for p in candidates:
    if (p+1)/2 in candidates:
        similar.append(p)

answers = []
n = int(input())
for q in range(n):
    [l, r] = [int(i) for i in input().split()]
    answers.append(sum([l <= p <= r for p in similar]))

for a in answers:
    print(a)

### FIXED CODE ###

s = int(input())
print(24-s + 24)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for i in range(M)]
AB.reverse()
island = [[i+1] for i in range(N)]
ans = []
for m in range(M):
    count = 0
    for i in range(len(island)):
        for j in range(i+1, len(island)):
            count += len(island[i]) * len(island[j])
    ans.append(count)

    A, B = AB.pop(0)
    idxs = [None, None] # A, B
    for idx in range(len(island)):
        if A in island[idx]:
            idxs[0] = idx
        if B in island[idx]:
            idxs[1] = idx
        if None not in idxs:
            break
    if idxs[0] != idxs[1]:
        island[idxs[0]].extend(island[idxs[1]])
        del island[idxs[1]]

ans.reverse()
[print(ans[i]) for i in range(M)]

### FIXED CODE ###

def find(idx):
    global tree
    while True:
        if tree[idx].root == True:
            return tree[idx].prev, tree[idx].size
        else:
            idx = tree[idx].prev

class Union_Find:
    def __init__(self, prev):
        self.root = True
        self.size = 1
        self.prev = prev

N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for i in range(M)]
AB.reverse()
ans = [(N*(N-1))//2]
tree = {i:Union_Find(i) for i in range(1, N+1)}

for A, B in AB[:-1]:
    root_A, size_A = find(A)
    root_B, size_B = find(B)

    if root_A == root_B:
        ans.append(ans[-1])
    else:
        if size_A > size_B:
            x, y = root_B, root_A
        else:
            x, y = root_A, root_B

        tree[x].root = False
        tree[x].prev = y
        tree[y].size += tree[x].size

        ans.append(ans[-1] - size_A * size_B)

[print(max(0, i)) for i in ans[::-1]]
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split( )))
c = 1
for i in range(1,N):
    v = min(set(P[:i]))
    if v >= P[i]:
        c += 1
print(c)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split( )))
c = 1
v = P[0]
for i in range(1,N):
    if v >= P[i]:
        c += 1
        v = P[i]
print(c)
### BUGGY CODE ###

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

s = [0]*n

for i in range(n):
    s[i] = sum(A[i+1:])


tot = 0
for i in range(n-1):
    tot += A[i]*s[i]
    
print(tot%(10**9+7))

### FIXED CODE ###

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

a = A[::-1]
s = [0]*(n+1)

for i in range(n):
    s[i+1] = s[i] + a[i]

s = s[:n]
s = s[::-1]

tot = 0
for i in range(n-1):
    tot += A[i]*s[i]
    
print(tot%(10**9+7))
### BUGGY CODE ###

import sys

def longestcommonsubsequence():
    seq1 = raw_input()
    seq2 = raw_input()

    a, b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1+[]
        #x1 = [0 for i2 in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1] = x2[j] + 1
            else:
                x1[j+1] = max(x1[j+1], x1[j])
    return x1[-1]

n = input()
for i2 in range(n):

    print longestcommonsubsequence()

### FIXED CODE ###

import sys

def longestcommonsubsequence():
    seq1 = raw_input()
    seq2 = raw_input()

    a, b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1+[]
        #x1 = [0 for i2 in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1]<x1[j]:
                x1[j+1] = x1[j]
    return x1[-1]

n = input()
for i2 in range(n):

    print longestcommonsubsequence()
### BUGGY CODE ###

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

one2 = []
toN = []

for _ in range(M):
    a, b = map(int, input().split())

    if a == 1:
        one2.append(b)

    if b == N:
        toN.append(a)

flag = False
for a in one2:
    if a in toN:
        flag = True
        break

if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

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

one2 = set()
toN = set()

for _ in range(M):
    a, b = map(int, input().split())

    if a == 1:
        one2.add(b)

    if b == N:
        toN.add(a)

inter = one2 & toN

if len(inter) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

l = raw_input().split()
s = l[0]

def get_removals(s):
    ret = []
    for i in range(len(s) - 1):
        if int(s[i]) + int(s[i + 1]) == 1:
            ret.append(i)
    return ret

def remove(s, index):
    if index == 0:
        return s[2:]
    if index == (len(s) - 1):
        return s[:index-1]
    return  s[0:index] + s[index + 2:]

num_removals = []

def process(s, count):
    removals = get_removals(s)
    if len(removals) == 0:
        num_removals.append(count)
        return
    count += 2
    for removal in removals:
        s1 = remove(s, removal)
        process(s1, count)

process(s, 0)
print(max(num_removals))


### FIXED CODE ###

l = raw_input().split()
s = l[0]

def get_removals(s):
    ret = []
    for i in range(len(s) - 1):
        if int(s[i]) + int(s[i + 1]) == 1:
            ret.append(i)
    return ret

def remove(s, index):
    if index == 0:
        return s[2:]
    if index == (len(s) - 1):
        return s[:index-1]
    return  s[0:index] + s[index + 2:]

num_removals = []

ones = 0
zeros = 0
for num in s:
    if num == '0':
        ones += 1
    if num == '1':
        zeros += 1
max_candidate = min(ones, zeros) * 2

def process(s, count):
    removals = get_removals(s)
    if len(removals) == 0:
        num_removals.append(count)
        if count == max_candidate:
            print(max_candidate)
            exit()
        return
    count += 2
    max_remove = 0
    ss = []
    for removal in removals:
        s1 = remove(s, removal)
        ss.append(s1)
        num_removes = len(get_removals(s1))
        if max_remove < num_removes:
            max_remove = num_removes
    for s1 in set(ss):
        if len(get_removals(s1)) == max_remove:
            process(s1, count)

# process(s, 0)
print(max_candidate)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
M = 1000000007
sm = 0
for i in range(n):
	for j in range(i+1,n):
		sm = (sm%M + (l[i] * l[j])%M) % M
print(sm)


### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
M = 1000000007
sm = 0
for i in l:
	sm = (sm + i)
sms = pow(sm,2)
ss = 0
for i in range(n):	
	ss = (ss + (l[i] * l[i]))
print(((sms - ss)//2)%M)