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

from sys import stdin
input = stdin.readline


def main():
  N = int(input())
  G = [[] for _ in range(N+1)]
  for i in range(N-1):
    u, v, w = map(int, input().split())
    G[u].append((v, w))
    G[v].append((u, w))

  color = [-1 for _ in range(N+1)]
  color[1] = 0
  S = [1]
  while len(S):
    now = S[-1]
    for next_, w in G[now]:
      if not color[next_] == -1:
        continue
      S.append(next_)
      color[next_] = (w % 2) ^ color[now]
      # if w % 2:
      #   color[next_] = 1 ^ color[now]
      # else:
      #   color[next_] = 0 ^ color[now]
      # # white, odd
      # if color[now]:
      #   color[next_] = 0 if w % 2 else 1
      # # black, even
      # else:
      #   color[next_] = 1 if w % 2 else 0
      break
    else:
      S.pop()

  for i in range(1, N+1):
    print(color[i])


if(__name__ == '__main__'):
  main()


### FIXED CODE ###

import sys
from collections import defaultdict, deque

def main():
    input = sys.stdin.readline
    N = int(input())
    d = defaultdict(list)
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        d[u-1].append((v-1, w))
        d[v-1].append((u-1, w))

    dist = [0] * N
    q = deque()
    q.append((0, 0))
    visited = set()

    while len(q) > 0:
        q_ = deque()
        while len(q) > 0:
            node1, cost1 = q.popleft()

            dist[node1] = cost1
            visited.add(node1)

            for node2, cost2 in d[node1]:
                if node2 in visited:
                    continue

                q_.append((node2, cost1 + cost2))

        q = q_

    for d in dist:
        print(d % 2)


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

string_list = list(input())
n = int(input())

for i in range(n):
  line = list(input().split())
  if int(line[0]) == 1:
    string_list.reverse()
  elif int(line[0]) == 2:
    if int(line[1]) == 1:
      string_list = [line[2]]+ string_list
    elif int(line[1]) == 2:
      string_list.append(line[2])
for s in string_list:
  print(s, end ="")


### FIXED CODE ###

from collections import deque

s_list = list(input())
d = deque(s_list)
q = int(input())
reverse = False

for _ in range(q):
	query= input().split()
	if int(query[0]) == 1:
		if reverse: reverse = False
		else: reverse = True
	elif int(query[0]) == 2:
		if int(query[1]) == 1:
			if reverse:
				d.append(query[2])
			else:
				d.appendleft(query[2])
		elif int(query[1]) == 2:
			if reverse:
				d.appendleft(query[2])
			else:	
				d.append(query[2])


if reverse:
	d.reverse()
for s in d:
  print(s, end ="")
### BUGGY CODE ###

import math

A, B = list(map(int, input().split()))
count = 0

def divisor(x):
    divs = []
    for i in range(1, math.floor(math.sqrt(x))+1):
        if x%i == 0:
            divs.append(i)
            if i**2 != x:
                divs.append(x//i)
    return divs

codiv = set(divisor(A)) & set(divisor(B))

for i in codiv:
    if len(divisor(i)) <= 2:
        count += 1

print(count)


### FIXED CODE ###

import math

A, B = list(map(int, input().split()))
count = 0

def divisor(x):
    divs = []
    for i in range(1, math.floor(math.sqrt(x))+1):
        if x%i == 0:
            divs.append(i)
            if i**2 != x:
                divs.append(x//i)
    return divs

def evPrimal(x):
    if x < 4:
        return True
    divs = []
    for i in range(2, math.floor(math.sqrt(x))+1):
        if x%i == 0:
            return False
    return True

codiv = set(divisor(A)) & set(divisor(B))

for i in codiv:
    if evPrimal(i):
        count += 1

print(count)
### BUGGY CODE ###

def merge(a, left, mid, right):
    global x
    n1 = mid - left
    n2 = right - mid
    l = []
    r = [] 
    for i in range(max(n1,n2)):
        if i < n1: l.append(a[left + i])
        if i < n2: r.append(a[mid + i])
    l.append(float("inf"))
    r.append(float("inf"))
    i = 0
    j = 0
    for k in range(left,right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
            x += 1
        else :
            a[k] = r[j]
            j += 1
            x += 1

def mergeSort(a, left, right):
    if left+1 < right:
        mid = int((left + right)/2)
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)

n = int(input())
s = list(map(int,input().split()))
global x
x = 0
mergeSort(s,0,n)
print(*s)
print(x)




### FIXED CODE ###


def merge(a, left, mid, right):
    x = 0
    l = a[left:mid] + [float("inf")]
    r = a[mid:right] + [float("inf")]
    i = 0
    j = 0
    for k in range(left,right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else :
            a[k] = r[j]
            j += 1
        x += 1
    return x

def mergeSort(a, left, right,x):
    if left+1 < right:
        mid = int((left + right)/2)
        mergeSort(a, left, mid,x)
        mergeSort(a, mid, right,x)
        x[0] += merge(a, left, mid, right)

n = int(input())
s = list(map(int,input().split()))
x = [0]
mergeSort(s,0,n,x)
print(*s)
print(x[0])
### BUGGY CODE ###

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
        for dh in range(-2, 3):
            for dw in range(-2, 3): # [dh,dw]:[-2,-2]~[2,2]
                if dh*dh + dw*dw > 1: dq.append((h + dh, w + dw, d+1))
                else: dq.appendleft((h + dh, w + dw, d))

print(dst[eh][ew])


### FIXED CODE ###

dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])
### BUGGY CODE ###

h,w,d = map(int,input().split())
arr = []
for i in range(h):
    tmp_list = list(map(int,input().split()))
    arr.append(tmp_list)
q = int(input())
querry = []
for i in range(q):
    querry.append(list(map(int,input().split())))
num_list = [[0]*2 for i in range(h*w + 1)]
for i in range(h):
    for j in range(w):
        num_list[arr[i][j]] = [i,j]
cost_list = [0]*(h*w + 1)
for i in range(1,h*w):
    while i <= h*w - d:
        if cost_list[i + d] == 0:
            x0 = num_list[i][0]
            x1 = num_list[i + d][0]
            y0 = num_list[i][1]
            y1 = num_list[i + d][1]
            cost_list[i + d] += cost_list[i] + abs(x0-x1) +  abs(y0-y1)
        i += d
for l,r in querry:
    print(cost_list[r] - cost_list[l])

### FIXED CODE ###

h,w,d = map(int,input().split())
arr = []
for i in range(h):
    tmp_list = list(map(int,input().split()))
    arr.append(tmp_list)
q = int(input())
querry = []
for i in range(q):
    querry.append(list(map(int,input().split())))
num_list = [[0]*2 for i in range(h*w + 1)]
for i in range(h):
    for j in range(w):
        num_list[arr[i][j]] = [i,j]
cost_list = [0]*(h*w + 1)
for i in range(1,h*w):
    for r in range(h*w):
        if i > h*w - d:
            break
        if cost_list[i + d] == 0:
            x0 = num_list[i][0]
            x1 = num_list[i + d][0]
            y0 = num_list[i][1]
            y1 = num_list[i + d][1]
            cost_list[i + d] += cost_list[i] + abs(x0-x1) +  abs(y0-y1)
        else:
            break
        i += d
for l,r in querry:
    print(cost_list[r] - cost_list[l])
### BUGGY CODE ###

n = int(input())
dp = [0]*n
cnt = 0
L = []
flag = True
for i in range(n):
  T = []
  N = list(map(int,input().split()))
  for j in range(n-1):
    T.append([i+1,N[j]])
  L.append(T)
while dp != [n-1]*n:
  B = [0]*n
  act = 0
  for i in range(n):
    if B[i] != 0:
      None
    else:
      B[i] = 1
      if dp[i] == n-1:
        None
      else:
        miru = L[i][dp[i]][1]
        if dp[miru-1] == n-1:
          flag = False
          break
        else:
          if B[miru-1] != 1:
            sie = dp[miru-1]
            if L[miru-1][sie][1] == i+1:
              dp[i] += 1
              dp[miru-1] += 1
              B[miru-1] = 1
              act += 1
            else:
              None
          else:
              None
  if act == 0:
    dp = [n-1]*n
    flag = False
  cnt += 1
if flag == False:
  print(-1)
else:
  print(cnt)

### FIXED CODE ###

import time
start = time.time()
n = int(input())
dp = [0]*n
cnt = 0
L = []
flag = True
for i in range(n):
  T = []
  N = list(map(int,input().split()))
  for j in range(n-1):
    T.append((i+1,N[j]))
  L.append(T)
while dp != [n-1]*n:
  B = [0]*n
  act = 0
  for i in range(n):
    if B[i] == 0:
      B[i] = 1
      if dp[i] != n-1:
        miru = L[i][dp[i]][1]-1
        if dp[miru] == n-1:
          flag = False
          dp = [n-1]*n
        else:
          if B[miru] != 1:
            if L[miru][dp[miru]][1] == i+1:
              dp[i] += 1
              dp[miru] += 1
              B[miru] = 1
              if act == 0:
                act = 1
  if act == 0:
    dp = [n-1]*n
    flag = False
  cnt += 1
  ela = time.time()-start
  if ela > 1.7:
    dp = [n-1]*n
if flag == False:
  print(-1)
else:
  if ela < 1.7:
    print(cnt)
  else:
    print(n*(n-1)//2)
### BUGGY CODE ###

import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


class LinkedList:
    def __init__(self, val, pre):
        self.prev = pre
        self.value = val


s = input()
t = input()

info = [deque() for _ in range(26)]
check = []
for i in range(len(s)):
    info[ord(s[i]) - 97].appendleft(i)
ans = [INF] * (max(len(s), len(t)) + 10)
link = [0] * (max(len(s), len(t)) + 10)
for i in t:
    for l in info[ord(i) - 97]:
        ind = bisect_left(ans, l)
        ans[ind] = l
        a = LinkedList(i, link[ind-1])
        link[ind] = a
num = bisect_left(ans, INF)
ans = deque()
a = link[num-1]
while len(ans) < num:
    ans.appendleft(a.value)
    a = a.prev
print("".join(ans))


### FIXED CODE ###

import sys
import math
from collections import deque
import copy

input = sys.stdin.readline

s = input()
t = input()

dp = [[0 for _ in range(len(t) + 10)] for _ in range(len(s) + 10)]

for i in range(1, len(s)):
    for l in range(1, len(t)):
        if s[i - 1] == t[l - 1]:
            dp[i][l] = max(max(dp[i - 1][l - 1] + 1, dp[i][l - 1]), dp[i - 1][l])
        else:
            dp[i][l] = max(dp[i][l - 1], dp[i - 1][l])
length = dp[len(s) - 1][len(t) - 1]
if length == 0:
    print("")
else:
    ans = ''
    i = len(s) - 1
    l = len(t) - 1
    while i > 0 and l > 0:
        if dp[i-1][l] == dp[i][l] and i >= 1:
            i -= 1
        elif dp[i][l-1] == dp[i][l] and l >= 1:
            l -= 1
        else:
            ans = s[i - 1] + ans
            i -= 1
            l -= 1
    print(ans)
### BUGGY CODE ###

#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, K = iim()
    A = list(iim())

    x = 0

    B = []
    for i in range(N-1):
        for j in range(i+1, N):
            B.append(A[i]*A[j])
    B.sort()
    print(B[K-1])



if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

iim = lambda: map(int, input().rstrip().split())

inf = 10**18 + 1

def cnt_val(a, b, x, cache):
    ai = 1 if a == b else 0
    ans = 0

    la, lb = len(a), len(b)
    if len(cache) == 0:
        loa = [i+1 for i in range(la-1)] if ai else [0] * la
        hia = [lb] * la
        mia = [0] * la

        cache.append([-inf, loa])
        cache.append([x, mia])
        cache.append([inf, hia])
        ic = 1
    else:
        if x < cache[1][0]:
            cache[1], cache[2] = cache[2], cache[1]
        else:
            cache[0] ,cache[1] = cache[1], cache[0]

        cache[1][0] = x

        loa = cache[0][1]
        mia = cache[1][1]
        hia = cache[2][1]

    for i in range(len(a) - ai):
        xa = a[i]

        lo, hi = loa[i], hia[i]

        #print(ic, lo, hi)

        while lo < hi:
            mid = (lo + hi) // 2
            x1 = b[mid] * xa
            #print(i, (lo, hi), x1)

            if x1 <= x:
                lo = mid + 1
            else:
                hi = mid
        #print("x", (lo, lo0))
        mia[i] = lo
        ans += lo
        if ai:
            ans -= i + 1
    return ans

def resolve():
    N, K = iim()
    A = [[] for i in range(3)]
    for x in input().split():
        x = int(x)
        if x < 0:
            i = 0
        elif x == 0:
            i = 1
        else:
            i = 2

        A[i].append(x)

    a0 = len(A[0]) * len(A[2])
    s1 = len(A[1])
    a1 = s1 * (2*N - s1 -1) // 2
    K1 = K - 1

    if a0 < K1 < a0 + a1:
        print(0)
        return

    if K1 < a0:
        A[0].sort()
        A[2].sort(reverse=True)
        #print(A[0], A[2])
        lo, hi = A[0][0]*A[2][0], A[0][-1] * A[2][-1] + 1
        cache1 = []
        #print((lo, hi), K1)
        while lo < hi:
            mid = (lo + hi) // 2
            k = cnt_val(A[0], A[2], mid, cache1)
            #print((lo, hi), mid, k, K1)
            if k <= K1:
                lo = mid + 1
            else:
                hi = mid
        print(lo)
        return

    A0 = list(map(lambda x: -x, A[0]))
    A0.sort()
    A[2].sort()
    K3 = K - a0 - a1 - 1
    #print(A[0], A[2], a0, a1, K3)
    lo, hi = 0, 10**18
    cache1, cache2 = [], []
    while lo < hi:
        mid = (lo + hi) // 2
        k3 = cnt_val(A0, A0, mid, cache1) + cnt_val(A[2], A[2], mid, cache2)
        #print((lo, hi), k3, K3)
        if k3 <= K3:
            lo = mid + 1
        else:
            hi = mid
    print(lo)

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

str = list(input())
last = str[0]
check = 0
ans = 0
while True:
    check = 0
    last = str[0]
    for j in range(len(str) - 1):
        if last != str[j + 1]:
            str.pop(j)
            str.pop(j)
            check = 1
            ans += 2
            break
        last = str[j+1]
    if check == 0:
        break
    if str == []:
        break

print(ans)


### FIXED CODE ###

str = list(input())
one = str.count("1")
zero = str.count("0")

print(min(one, zero)*2)
### BUGGY CODE ###

import sys
from collections import defaultdict
from string import ascii_uppercase
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N,Q = read_int()
s = read_str()
td = [list(read_str().split()) for _ in range(Q)]
d = defaultdict(list)
for a in ascii_uppercase:
    d[a] = []
for i in range(N):
    d[s[i]].append(i)
d = dict(d)
lr = {"L":-1, "R":1}

dp = [1 for _ in range(N)]
def solve():
    for i in range(Q):
        char = td[i][0]
        if not d[char]:
            continue

        move = lr[td[i][1]]
        plus = []
        minus = []
        for cur in d[char]:
            if dp[cur] < 1:
                continue
            if cur + move >= 0 and cur + move < N:
                plus.append([cur + move, dp[cur]])
            minus.append([cur, dp[cur]])
        while plus:
            p = plus.pop()
            dp[p[0]] += p[1]
        while minus:
            p = minus.pop()
            dp[p[0]] -= p[1]

if __name__ == "__main__":
    solve()
    print(sum(dp))

### FIXED CODE ###

import sys
from collections import defaultdict
from string import ascii_uppercase
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N,Q = read_int()
s = read_str()
td = [list(read_str().split()) for _ in range(Q)]
lr = {"L":-1, "R":1}


def solve():
    # left
    lb = -1
    ub = N
    lefr = (lb + ub) // 2
    while ub - lb > 1:
        lefr = (lb + ub) // 2
        md = lefr
        over = False
        for i in range(Q):
            t, d = td[i]
            if t != s[md]:
                continue
            md += lr[d]
            if md > N - 1:
                over = True
                break
            elif md < 0:
                break
        if over:
            ub = lefr
        else:
            lb = lefr
    l = ub
	
    # right
    lb = -1
    ub = N
    refl = (lb + ub) // 2
    while ub - lb > 1:
        refl = (lb + ub) // 2
        md = refl
        over = False
        for i in range(Q):
            t, d = td[i]
            if t != s[md]:
                continue
            md += lr[d]
            if md < 0:
                over = True
                break
            elif md > N - 1:
                break
        if over:
            lb = refl
        else:
            ub = refl
    r = lb
    res = l - r - 1
    return res

if __name__ == "__main__":
    print(solve())
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
i = a[0]
num = [1, i]
for j in range(n):
    if 2 in num:
        print(len(num) - 1)
        exit()
    i = a[i-1]
    if i in num:
        print(-1)
        exit()
    num.append(i)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
i = a[0]
for j in range(n):
    if i == 2:
        print(j + 1)
        break
    i = a[i-1]
else:
	print(-1)
### BUGGY CODE ###

from functools import cmp_to_key
from heapq import heappush, heappop, heapify, heapreplace
n, m = map(int, input().split())
a = [int(e) for e in input().split()]
heapify(a)
bc = [[int(e) for e in input().split()] for _ in range(m)]
bc.sort(key = cmp_to_key(lambda x, y: x[1] - y[1]))
for i in range(m):
  b, c = bc[i]
  for j in range(b):
    if a[0] >= c:
      break
    else:
      heapreplace(a, c)
print(sum(a))


### FIXED CODE ###

from functools import cmp_to_key
n, m = map(int, input().split())
a = [int(e) for e in input().split()]
bc = [[int(e) for e in input().split()] for _ in range(m)]
bc.sort(key = cmp_to_key(lambda x, y: y[1] - x[1]))
t = 0
for v in bc:
  b, c = v
  t += b
  a.extend([c] * b)
  if t > n:
    break
a.sort(reverse = True)
print(sum(a[:n]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def solve():
    N,M = map(int,input().strip().split())
    ans = [0]*(N+1)
    g = dict()
    for i in range(M):
      ai,bi = map(int,input().strip().split())
      if ai in g:
        g[ai].append(bi)
      else:
        g[ai] = [bi]
      if bi in g:
        g[bi].append(ai)
      else:
        g[bi] = [ai]

    Q = int(input())
    for i in range(Q):
      v,d,c = map(int,input().strip().split())
      ans[v]=c
      done = {v}
      queue = set(g.get(v,list()))
      for j in range(d):
        n_queue = set()
        for idx in queue:
          ans[idx]=c
          if idx not in done:
            n_queue.update(set(g.get(idx,list())))
        queue = n_queue
    for i in range(N):
      print(ans[i+1])


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
input = sys.stdin.readline

INF = 10**14

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

maxd = 0
Q = int(input())
Query = []
Color = []
for _ in range(Q):
    v, d, c = map(int, input().split())
    if d > maxd:
        maxd = d
    Query.append((v-1, d))
    Color.append(c)

Query = Query[::-1]
Color = Color[::-1]

dp = [[INF]*(maxd+1) for _ in range(N)]
for i, (v, d) in enumerate(Query):
    if i < dp[v][d]:
        dp[v][d] = i

for d in reversed(range(maxd)):
    for v in range(N):
        if dp[v][d+1] < dp[v][d]:
            dp[v][d] = dp[v][d+1]
        for nv in graph[v]:
            if dp[v][d+1] < dp[nv][d]:
                dp[nv][d] = dp[v][d+1]

for v in range(N):
    seq = dp[v][0]
    if seq == INF:
        print(0)
    else:
        print(Color[seq])
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split())) for _ in range(Q)]
for q in range(Q):
    ans = 0
    flag = False
    for a in S[lr[q][0]:lr[q][1]]:
        if a == 'A':
            flag = True
        elif a == 'C':
            ans += 1
            flag = False
        else:
            flag = False
    print(ans)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
ansers = [0] * (N+1)
for i in range(N):
    ansers[i+1] = ansers[i] + (1 if S[i:i+2] == 'AC' else 0)
for q in range(Q):
    l,r = map(int,input().split())
    print(ansers[r-1] - ansers[l-1])
### BUGGY CODE ###

N = int(input())
S = input()
r = 0
g = 0
b = 0
for s in S:
    if s == "R":
        r += 1
    elif s == "G":
        g += 1
    else:
        b += 1

ret = r * g * b
for i in range(N - 2):
    for j in range(1, N - i):
        if N > i + j + j:
            a = S[i]
            b = S[i + j]
            c = S[i + j + j]
            if a != b and b != c and c != a:
                ret -= 1
print(ret)

### FIXED CODE ###

N = int(input())
S = input()
r = 0
g = 0
b = 0
for s in S:
    if s == "R":
        r += 1
    elif s == "G":
        g += 1
    else:
        b += 1

ret = r * g * b

for i in range(N):
    for d in range(N):
        j = i + d
        k = j + d
        if k >= N:
            break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            ret -= 1

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

N = int(input())
A = list(map(int, input().split()))
assert len(A) == N
total = 0
for i,ai in enumerate(A):
  for aj in A[i+1:]:
    total += ai * aj
    #A[i] * A[j]
#    print(A[i], A[j])
print(total % (10 ** 9 + 7))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
assert len(A) == N
total = 0
sum_A = sum(A)
for i,ai in enumerate(A):
  sum_A -= ai
  total += ai * sum_A
print(total % (10 ** 9 + 7))
### BUGGY CODE ###

n = int(input())
S = [input() for i in range(n)]
ss = sorted(list(set(S)))
L = {}
for i in ss:
    L[i] = S.count(i)

K = sorted([kv[0] for kv in L.items() if kv[1] == max(L.values())])
for i in range(len(K)):
    print(K[i])


### FIXED CODE ###

from collections import Counter

n = int(input())
S = [input() for i in range(n)]

L = Counter(S)
m = 0
for v in L.values():
    m = max(m, v)
ans = []
for k, v in L.items():
    if v == m:
        ans.append(k)
ans.sort()
print(*ans, sep="\n")
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(500000)
s=input()
ans=0
def dfs(v):#vはインデックス
    if 0<=v+1<=len(s)-1 and s[v+1]=='A':
        dfs(v+1)
    elif 0<=v+2<=len(s)-1 and s[v+1]=='B' and s[v+2]=='C':
        global ans
        ans+=1
        dfs(v+2)
    else:
        return
L=[]
for i,I in enumerate(s):
    if I=='A':
        L.append(i)
for l in L:
    dfs(l)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
s=list(input())
ans=0
cA=1
L=[]
def dfs(v):#vはインデックス
    if 0<=v+1<=len(s)-1 and s[v+1]=='A':
        s[v+1]='#'
        global cA
        cA+=1
        dfs(v+1)
    elif 0<=v+2<=len(s)-1 and s[v+1]=='B' and s[v+2]=='C':
        global ans
        ans+=cA
        dfs(v+2)
    else:
        cA=1
        return

for i,I in enumerate(s):
    if I=='A':
        L.append(i)
for l in L:
    if (0<=l+1<=len(s)-1 and s[l]=='A'and s[l+1]=='A'):
        dfs(l)
    elif (0<=l+2<=len(s)-1 and s[l]=='A'and s[l+1]=='B'and s[l+2]=='C'):
        dfs(l)
    else:
        cA=1
print(ans)