Harryxun/stf_run huggingface dataset:
#!/usr/bin/env pypy3

import math
import itertools


INVALID = -1
INF = 10 ** 12


def dijkstra_dense(num_vs, adj_matrix, source, dest):
    dist = [INF for _ in range(num_vs)]
    visited = [False for _ in range(num_vs)]
    dist[source] = 0
    while True:
        u = min((j for j in range(num_vs) if not visited[j]),
                key=lambda i: dist[i], default=INVALID)
        if u == INVALID or dist[u] == INF:
            break
        visited[u] = True
        for v in range(num_vs):
            w = adj_matrix[u][v]
            if u != v and w < INF:
                new_len = dist[u] + w
                if new_len < dist[v]:
                    dist[v] = new_len
    return dist[dest]


def main():
    # 始点を頂点0、終点を頂点N + 1とする
    x0, y0, xf, yf = (int(x) for x in input().split())
    n = int(input())
    xs = [None for _ in range(n + 2)]
    ys = [None for _ in range(n + 2)]
    rs = [None for _ in range(n + 2)]
    xs[0], ys[0], rs[0] = x0, y0, 0
    xs[n + 1], ys[n + 1], rs[n + 1] = xf, yf, 0
    for i in range(1, n + 1):
        xs[i], ys[i], rs[i] = (int(z) for z in input().split())
    adj_matrix = [[INF for _ in range(n + 2)] for _ in range(n + 2)]
    for i, j in itertools.product(range(n + 2), repeat=2):
        adj_matrix[i][j] = max(0, math.hypot(xs[i] - xs[j],
                                             ys[i] - ys[j]) - (rs[i] + rs[j]))
    res = dijkstra_dense(n + 2, adj_matrix, 0, n + 1)
    print("{:.12f}".format(res))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import math
import itertools


INVALID = -1
INF = 10 ** 12


def dijkstra_dense(num_vs, adj_matrix, source, dest):
    dist = [INF for _ in range(num_vs)]
    visited = [False for _ in range(num_vs)]
    dist[source] = 0
    while True:
        u = min((j for j in range(num_vs) if not visited[j]),
                key=lambda i: dist[i], default=INVALID)
        if u == INVALID or dist[u] == INF:
            break
        visited[u] = True
        for v in range(num_vs):
            w = adj_matrix[u][v]
            if u != v and w < INF:
                new_len = dist[u] + w
                if new_len < dist[v]:
                    dist[v] = new_len
    return dist[dest]


def main():
    # 始点を頂点0、終点を頂点N + 1とする
    x0, y0, xf, yf = (int(x) for x in input().split())
    n = int(input())
    xs = [None for _ in range(n + 2)]
    ys = [None for _ in range(n + 2)]
    rs = [None for _ in range(n + 2)]
    xs[0], ys[0], rs[0] = x0, y0, 0
    xs[n + 1], ys[n + 1], rs[n + 1] = xf, yf, 0
    for i in range(1, n + 1):
        xs[i], ys[i], rs[i] = (int(z) for z in input().split())
    adj_matrix = [[INF for _ in range(n + 2)] for _ in range(n + 2)]
    for i, j in itertools.product(range(n + 2), repeat=2):
        adj_matrix[i][j] = max(0, math.hypot(xs[i] - xs[j],
                                             ys[i] - ys[j]) - (rs[i] + rs[j]))
    res = dijkstra_dense(n + 2, adj_matrix, 0, n + 1)
    print("{:.12f}".format(res))


if __name__ == '__main__':
    main()
n = int(input())
a = list(map(int,input()split()))
l =[]
k = 0
for i in range(n):
  if a[i]>=a[i-1]:
    l[k] += 1
  else:
    k += 1
print(max(l))
    

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
l = [0]
k = 0
for i in range(n-1):
  if a[i]>=a[i+1]:
    l[k] += 1   
  else:
    k += 1
    l.append(0)
print(max(l))
a = [int(input()) for i in range(3)]

if a[0] == 2:
  print(a[1] + a[2])
  
elif a[0] == 1:
  print('Hello World')


### FIXED CODE ###

N = int(input())

if N == 1:
  print('Hello World')
  
elif N == 2:
  print(int(input()) + int(input()))
n,k = (int(x) for x in input().split())
h = list(map(int, input().split()))

h.sort()#身長をソート.デフォルトは昇順なので降順(reverse=True)としておく
i=0
while h[i]<k:
  i+=1
  
print(n-i)

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
 
cnt = 0
for i in range(len(h)):
    if h[i] >= K:
        cnt += 1 
print(cnt)
N,K = map(int,input().split())
hp = list(map(int,input().split()))
hp_sort = sorted(hp,reverse = True)
if K < len(hp):
    for i in range(K):
        del hp_sort[i]
    print(sum(hp_sort))
else:
    print('0')


### FIXED CODE ###

N,K = map(int,input().split())
hp = list(map(int,input().split()))
hp_sort = sorted(hp)
if K < N:
    print(sum(hp_sort[0:N-K]))
else:
    print('0')
n, m, k = map(int, input().split(" "))

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

for i in range(1, n):
    a[i] += a[i - 1]
for i in range(1, m):
    b[i] += b[i - 1]

j,mx= m-1,0
for i in range(n):
    if a[i]>k:
        break
    while(b[j]>k-a[i]):
        j-=1
    if (i+j+2>mx):
        mx=i+j+2
print(mx)

### FIXED CODE ###

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

a = [0]+list(map(int, input().split(" ")))
b = [0]+list(map(int, input().split(" ")))

for i in range(1, n+1):
    a[i] += a[i - 1]
for i in range(1, m+1):
    b[i] += b[i - 1]

j,mx= m,0
for i in range(n+1):
    if a[i]>k:
        break
    while(b[j]>k-a[i]):
        j-=1
    if (i+j>mx):
        mx=i+j
print(mx)
N,K=list(map(int,input().split()))
dis =N-K+1
if K >=2:
    print(dism-1)
elif K ==1:
    print(0)

### FIXED CODE ###

N,K=list(map(int,input().split()))
dis =N-K+1
if K >=2:
    print(dis-1)
elif K ==1:
    print(0)
import sys
input = sys.stdin.readline

from itertools import accumulate
from math import factorial


def comb(n, r):
    return factorial(n) / factorial(r) / factorial(n - r)


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

    nums = [0] * 1001

    for e in l:
        nums[e] += 1

    acm = list(accumulate(nums))

    l.sort()
    ans = 0
    tmp = [0] * 1001
    tmp2 = [0] * 1001
    for i in range(n-2):
        for j in range(i+1, n-1):
            a = l[i]
            b = l[j]
            k = min(1000, a+b-1)

            # b < c のときの数
            cnt = acm[k] - acm[b]

            # b == c のときの補正
            if nums[b] >= 3 and a == b and tmp[b] == 0:
                cnt += int(comb(nums[b], 3))
                tmp[b] = 1

            if nums[b] >= 2 and a != b and tmp2[b] == 0:
                cnt += int(comb(nums[b], 2))
                tmp2[b] = 1

            ans += cnt

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

from bisect import bisect_left


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

    l.sort()

    ans = 0
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            a = l[i]
            b = l[j]
            mx = bisect_left(l, a + b)
            ans += mx - j - 1

    print(ans)


if __name__ == "__main__":
    main()
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

plus_zero = []
minus = []

for i in a:
    if i >= 0:
        plus_zero.append(i)
    if i < 0:
        minus.append(-i)

from collections import deque

plus_zero = deque(sorted(plus_zero, reverse=True))
minus = deque(sorted(minus, reverse=True))
ans_lst = []

# 負
if len(plus_zero) == 0 and (k % 2) != 0:
    for _ in range(k):
        ans_lst.append(-minus.pop())
# 正 or 0
else:
    while len(ans_lst) != k:
        if len(ans_lst) == k-1:
            ans_lst.append(plus_zero.popleft())
        else:
            if len(plus_zero) < 2:
                ans_lst.append(minus.popleft())
                ans_lst.append(minus.popleft())
                continue
            elif len(minus) < 2:
                ans_lst.append(plus_zero.popleft())
                continue
            else:
                if (plus_zero[0] * plus_zero[1]) >= (minus[0] * minus[1]):
                    ans_lst.append(plus_zero.popleft())
                else:
                    ans_lst.append(minus.popleft())
                    ans_lst.append(minus.popleft())
                continue
ans = 1
for i in ans_lst:
    ans = (ans * i) % MOD
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

plus_zero = []
minus = []

for i in a:
    if i >= 0:
        plus_zero.append(i)
    if i < 0:
        minus.append(-i)

from collections import deque

plus_zero = deque(sorted(plus_zero, reverse=True))
minus = deque(sorted(minus, reverse=True))
ans_lst = []
# 境界条件: k == n
if k == n:
    ans_lst.extend(a)
# 負
elif len(plus_zero) == 0 and (k % 2) != 0:
    for _ in range(k):
        ans_lst.append(-minus.pop())
# 正 or 0
else:
    while len(ans_lst) != k:
        if len(ans_lst) == k-1:
            ans_lst.append(plus_zero.popleft())
        else:
            if len(plus_zero) == 0:
                ans_lst.append(minus.popleft())
                ans_lst.append(minus.popleft())
                continue
            if len(plus_zero) == 1:
                if (k - len(ans_lst)) % 2 == 0:
                    ans_lst.append(minus.popleft())
                    ans_lst.append(minus.popleft())
                else:
                    ans_lst.append(plus_zero.popleft())
                continue
            if len(minus) < 2:
                ans_lst.append(plus_zero.popleft())
                continue
            if len(plus_zero) >= 2 and len(minus) >= 2:
                if (plus_zero[0] * plus_zero[1]) >= (minus[0] * minus[1]):
                    ans_lst.append(plus_zero.popleft())
                else:
                    ans_lst.append(minus.popleft())
                    ans_lst.append(minus.popleft())
                continue
# functools.reduceはTLEをくらう場合があるので気をつける
ans = 1
for i in ans_lst:
    ans = (ans * i) % MOD
print(ans)
[W,H,x,y,r]=[int(x) for x in input().split()]
if (abs(x)=>r and abs(W-x)=>r) and (abs(y)=>r and abs(H-y)=>r):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

W,H,x,y,r=[int(x) for x in input().split()]
print("No" if x < r or y < r or (x+r) > W or (y+r) > H else "Yes")
def output(list):
    for i,row in enumerate(list):
        if i == 0:
            print(row,end='')
        else:
            print('',row,end='')
    
def main():
    s = input()
    s_list = []
    s_list = list(map(int,input().split()))

    output(s_list)
    print()

#print(list)
    start = time.time()
    i = 0
    for count in range(len(s_list)-1):

#   Judge: now > next
        if s_list[i] > s_list[i+1]:

#       Change: now > next
            ins_num = s_list[i+1]
            s_list[i+1] = s_list[i]
            s_list[i]   = ins_num

            j = i - 1

            while j >= 0:
                if s_list[j] > ins_num:
                    s_list[j+1] = s_list[j]
                    s_list[j]   = ins_num

                j -= 1
            output(s_list)
        else:
           output(s_list)        
    
        print()
        i += 1

    result = time.time() - start
#print(result)
#print(list)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def output(list):
    for i,row in enumerate(list):
        if i == 0:
            print(row,end='')
        else:
            print('',row,end='')
    
def main():
    s = input()
    s_list = []
    s_list = list(map(int,input().split()))

    output(s_list)
    print()

    i = 0
    for count in range(len(s_list)-1):

#   Judge: now > next
        if s_list[i] > s_list[i+1]:

#       Change: now > next
            ins_num = s_list[i+1]
            s_list[i+1] = s_list[i]
            s_list[i]   = ins_num

            j = i - 1

            while j >= 0:
                if s_list[j] > ins_num:
                    s_list[j+1] = s_list[j]
                    s_list[j]   = ins_num

                j -= 1
            output(s_list)
        else:
           output(s_list)        
    
        print()
        i += 1

if __name__ == '__main__':
    main()
print('bust') if sum(input().split()) >= 22 else print('win')

### FIXED CODE ###

print('bust') if (sum(map(int, input().split()))) >= 22 else print('win')
n,t=map(int,input().split())
c=[list(map(int,input().split())) for i in range(n)]
d=list()
s1=0
s2=0
d=[[c[i][1]/c[i][0],c[i][0],c[i][1]] for i in range(n)]
d=sorted(d,key=lambda x:(x[0],x[1]))
for i in range(n):
  s2+=d[i][2]
  s1+=d[i][1]
  if s1>=t-0.5:
    print(s2)
    exit()


### FIXED CODE ###

r=int(input())
print(r**2)
a = int(input())
b = int(input())
c = int(input())

if a == 5 and b == 7 and c == 5:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

a, b, c = map(int, input().split())
if a + b + c == 17:
  print("YES")
else:
  print("NO")
A,B = input().split(' ')
num = 0
for i in range(int(A), int(B)+1):
    s = str(i)
    for j in range(len(s)//2):
        if s[j] != s[len(s)-1-j]:
            break
        if j == len(s)//2 - 1:
            num += 1
print(num

### FIXED CODE ###

A,B = input().split(' ')
num = 0
for i in range(int(A), int(B)+1):
    s = str(i)
    for j in range(len(s)//2):
        if s[j] != s[len(s)-1-j]:
            break
        if j == len(s)//2 - 1:
            num += 1
print(num)
import collections

n = int(input())
s = [input() for i in range(n)]
w = ""

if n == 1:
    r = sorted(collections.Counter(s))
    for k, v in r.items():
        w += k * r[k]
    print(w)
    exit()
a = collections.Counter(s[0])
b = collections.Counter(s[1])
res = a & b
if n <= 2:
    for k in sorted(res):
        w += k * res[k]
    print(w)
else:
    for i in s[2:]:
        res = res & collections.Counter(i)
    if not res:
        print("")
    for k in sorted(res):
        w += k * res[k]
    print(w)


### FIXED CODE ###

import collections

n = int(input())
s = [input() for i in range(n)]
w = ""
if n == 1:
    r = collections.Counter(s[0])
    for k in sorted(r):
        w += k * r[k]
    print(w)
    exit()
a = collections.Counter(s[0])
b = collections.Counter(s[1])
res = a & b
if n <= 2:
    for k in sorted(res):
        w += k * res[k]
    print(w)
else:
    for i in s[2:]:
        res = res & collections.Counter(i)
    if not res:
        print("")
    for k in sorted(res):
        w += k * res[k]
    print(w)
A,B = map(int,input().split())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

comdiv = [] 
A_div = make_divisors(A)
for i in A_div:
  if B % i == 0:
    comdiv.append(i)

def Eratosthenes(n):

    dp = [False]*n#sその値が素数かどうかを格納する。Falseなら素数。#場合によってはこちらをreturnしても良い。
    dp[0] = dp[1] = True#0,1はそれぞれ素数ではないのでTrueを入れる
    prime = []#素数列
    for i in range(2,n):
        if dp[i]:
            continue#素数でなければcontinue
        prime.append(i)#素数であれば足す
        #以下、iより大きいiの倍数を除外する処理
        for j in range(i*2,n,i):
          dp[j] = True
    return prime
  
flg = [False] * (B + 1) 
  
Era = Eratosthenes(B+1)
for e in Era:
  flg[e] = True

cnt = 0
for i in comdiv:
  if flg[i] == True:
    cnt += 1
print(cnt+1)

### FIXED CODE ###

A,B = map(int,input().split())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

comdiv = [] 
div = make_divisors(A)
for i in div:
  if B % i == 0:
    comdiv.append(i)
#print(comdiv)

def isPrime(n):
  if n < 2:
    return False
  i = 2
  while i*i <= n:
    if n%i == 0:
      return False
    i += 1
  return True

cnt = 0
for i in comdiv:
  if isPrime(i):
    cnt += 1
print(cnt+1)
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

C_B = []
for _ in range(M):
    B, C = map(int, input().split())
    C_B.append([C, B])
C_B.sort(reverse = True)

sums = 0
now = 0
for j in range(M):
    #temp = A[now:now+C_B[j][1]]
    #print(temp)
    if C_B[j][0]>=A[now+C_B[j][1]]: #すべて置き換え
        sums += C_B[j][0]*C_B[j][1]
        now += C_B[j][1]
    elif C_B[j][0]<=A[now]: #置き換えない
        break
    else:
        sm = now
        la = C_B[j][1]-1
        md = C_B[j][1]//2
        p = C_B[j][0]
        while la-sm>1:
            if A[now+md]<p:
                sm=md
                md=(la-sm)//2
            elif A[now+md]==p:
                la=md
            else:
                la=md-1
                md=(la-sm)//2
        sums += la*p
        now += la
        break
#print(sums, now)
#残りを加算
if now<=N:
    for i in range(now, N):
        sums += A[i]
print(sums)

### FIXED CODE ###

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

CB = []
for i in range(M):
    b, c = map(int, input().split())
    CB.append([c, b])
CB.sort(reverse=True)
CBCB = [CB[0]]
for i in range(1, M):
    if CB[i][0]==CB[i-1][0]:
        CBCB[-1][1]+= CB[i][1]
    else:
        CBCB.append(CB[i])

ind = 0
ans=0
for l in CBCB:
    if A[ind]>l[0]: # 打ち切り
        break
    elif A[min(ind+l[1]-1, N-1)]<l[0]: #すべて置き換え
        if ind+l[1]>N-1:
            ans+=l[0]*(N-ind)
            ind = N
            break
        else:
            ans+=l[0]*l[1]
            ind+=l[1]
    else:
        sm = ind-1
        la = min(ind + l[1] -1 , N-1)
        while sm+1<la:
            md = (sm+la)//2
            if A[md]>=l[0]:
                la = md
            else:
                sm = md
        ans += l[0]*(sm-ind+1)
        ind = sm+1
        break
        
for i in range(ind, N):
    ans+=A[i]
print(ans)
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    if N in (1,3):
        raise Exception
    else:
        print("No")
if __name__ == '__main__':
    main()

### FIXED CODE ###

#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    N*=2
    size = -1
    group_num = -1
    for i in range(2,N+2):
        if i*(i-1)==N:
            group_num = i
            size = i-1
            break
    if size == -1:
        print("No")
        return 
    
    ans = [[-1]*size for _ in range(group_num)]

    now = 0
    for i in range(group_num):
        for j in range(size):
            if j<i:
                ans[i][j] = ans[j][i-1]
            else:
                now += 1
                ans[i][j] = now

        
    print("Yes")
    print(group_num)
    for a in ans:
        print(size,*a)

if __name__ == '__main__':
    main()
a,b=int(input().split())
if a<=9 and b<=9:
  print(a*b)
else:
  print(-1)


### FIXED CODE ###

a,b=map(int,input().split())
if a<=9 and b<=9:
  print(a*b)
else:
  print(-1)
H, W = map(int, input().split())

for i in range(W):
    C = input()
    print(C)
    print(C)


### FIXED CODE ###

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

for i in range(H):
    C = input()
    print(C)
    print(C)
N=int(input())
if N==1:
  print(1)
elif 2<=N<4
  print(2)
elif 4<=N<8:
  print(4)
elif 8<=N<16:
  print(8)
elif 16<=N<32:
  print(16)
elif 32<=N<64:
  print(32)
else:
  print(64)

### FIXED CODE ###

N=int(input())
if N==1:
  print(1)
elif 2<=N<4:
  print(2)
elif 4<=N<8:
  print(4)
elif 8<=N<16:
  print(8)
elif 16<=N<32:
  print(16)
elif 32<=N<64:
  print(32)
else:
  print(64)
import math
A = list(map(int, input().split()))
a = A[0]
b = A[1]

ans = a*b/math.gcd(a,b)
print(ans)

### FIXED CODE ###

A = list(map(int, input().split()))
a = A[0]
b = A[1]
 
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a
 
ans = a*b/gcd(a,b)
ans = int(ans)
print(ans)
N = int(input())
A = list(map(int,input().split()))
mod = 1000000000 + 7
add = 0
for i in range(N):
    tmp = sum(A[i+1:N])
    add += tmp * A[i]
print(add%mod

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 1000000000 + 7
add = 0
tmp = sum(A)
for i in range(N):
    tmp -= A[i]
    add += tmp * A[i]
print(add%mod)
import re
s = str(input())
n = len(s)
z = [0] * n
lr = [m.start() for m in re.finditer('LR', s)]
rl = [m.start() for m in re.finditer('RL', s)]
t = []
if lr == []:
    t = s
else:
    t.append(s[:lr[0]+1])
    for i in range(len(lr)-1):
        t.append(s[lr[i]+1 : lr[i+1]+1])
    t.append(s[lr[-1]+1:])

for i in range(len(t)):
    r = t[i].count('R')
    l = len(t[i]) - r
    # x : RL界面左側の数。y : RL界面右側の数。
    x = (r+1) // 2 + l // 2
    y = r // 2 + (l+1) // 2
    z[rl[i]] = x
    z[rl[i]+1] = y

delta = [str(i) for i in z]
ans = ' '.join(delta)
print(ans)

### FIXED CODE ###

import re
s = str(input())
n = len(s)
z = [0] * n
lr = [m.start() for m in re.finditer('LR', s)]
rl = [m.start() for m in re.finditer('RL', s)]
t = []
if lr == []:
    t.append(s)
else:
    t.append(s[:lr[0]+1])
    for i in range(len(lr)-1):
        t.append(s[lr[i]+1 : lr[i+1]+1])
    t.append(s[lr[-1]+1:])
for i in range(len(t)):
    r = t[i].count('R')
    l = len(t[i]) - r
    # x : RL界面左側の数。y : RL界面右側の数。
    x = (r+1) // 2 + l // 2
    y = r // 2 + (l+1) // 2
    z[rl[i]] = x
    z[rl[i]+1] = y

delta = [str(i) for i in z]
ans = ' '.join(delta)
print(ans)
import math
a, b, x = map(int, input().split())
if a*a*b<=2*x:
    print(90-math.degrees(math.atan(a**3/(2*b*a*a-2*x))))
else:
    print(90-math.degrees(math.atan(2*x/(a*b*b))))

### FIXED CODE ###

import math
a, b, x = map(int, input().split())
if a*a*b==x:
    print(0)
elif a*a*b<=2*x:
    print(90-math.degrees(math.atan(a**3/(2*b*a*a-2*x))))
else:
    print(90-math.degrees(math.atan(2*x/(a*b*b))))
daw = ["SUN","MON","TUE","WED","THU","FRI","SAT"]
S = input()
ind = S.find(daw)
print(7 - idx)


### FIXED CODE ###

daw = ["SUN","MON","TUE","WED","THU","FRI","SAT"]
S = input()
idx = daw.index(S)
print(7 - idx)
import sys
n=int(input())
a=list(map(int,input().split()))
s=sum(a)
if(n==2):
  mi=abs(a[0]-a[1])
else:
  s1=a[0]
  for i in range(1,len(a)-1):
    s1+=a[i]
    s2=s-s1
    #print(s1,s2)
    mi=min([mi,abs(s1-s2)])
print(mi)


### FIXED CODE ###

import sys
n=int(input())
a=list(map(int,input().split()))
s=sum(a)
if(n==2):
  mi=abs(a[0]-a[1])
else:
  mi=10**15
  s1=a[0]
  for i in range(1,len(a)-1):
    s1+=a[i]
    s2=s-s1
    #print(s1,s2)
    mi=min([mi,abs(s1-s2)])
print(mi)