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

import sys

import numpy as np

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


def dfs(s, n, sh, sw, gh, gw, c, ans):
    if n == 1:
        ans[sh:gh + 1, sw:gw + 1] = c
        c += 1
        return c
    # Horizontal division
    if s.shape[0] > 1:
        n_ = 0
        for h in range(gh - sh):
            n_ += np.sum(s[h, :])
            if 0 < n_ < n:
                c = dfs(s[:h+1, :], n_    , sh        , sw, sh + h, gw, c, ans)
                c = dfs(s[h+1:, :], n - n_, sh + (h+1), sw, gh    , gw, c, ans)
                return c
    # Vertical division
    n_ = 0
    for w in range(gw - sw):
        n_ += np.sum(s[:, w])
        if 0 < n_ < n:
            c = dfs(s[:, :w+1], n_    , sh, sw        , gh, sw + w, c, ans)
            c = dfs(s[:, w+1:], n - n_, sh, sw + (w+1), gh, gw    , c, ans)
            return c


def main():
    H, W, K = map(int, input().split())
    s = [None] * H
    s = np.full(shape=(H, W), fill_value=False, dtype=bool)
    for i in range(H):
        s[i] = [j == "#" for j in input().rstrip()]

    ans = np.zeros(shape=(H, W), dtype=int)
    _ = dfs(s, K, 0, 0, H - 1, W - 1, 1, ans)
    for i in range(H):
        print(" ".join(map(str, ans[i])))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

import numpy as np

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    s = np.zeros(shape=(H, W), dtype=np.bool)
    for i in range(H):
        s[i] = tuple(map(lambda x: True if x == "#" else False, input().rstrip()))

    ans = np.zeros(shape=(H, W), dtype=np.int64)
    h_keep = 0
    k = 1
    for h in range(H):
        if s[h].sum() > 0:
            indices = np.where(s[h])[0]
            ans[h_keep:h + 1] = k
            k += 1
            for idx in reversed(indices[:-1]):
                ans[h_keep:h + 1, :idx + 1] = k
                k += 1
            h_keep = h + 1
        else:
            h_keep = min(h_keep, h)

    if h_keep < H:
        h_base = h_keep - 1
        for h in range(h_keep, H):
            ans[h] = ans[h_base]

    for h in range(H):
        print(" ".join(map(str, ans[h])))


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

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, readl().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(readl().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    r = l
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans,Q


if __name__ == "__main__":
  ans,n = main()
  for _ in range(n):
    print(heappop(ans)[1])    


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

X = input()
MOD = 10**9 + 7
M = 13
S = [0]*M
S[0] = 1
T = [0]*M

def calc(S, T, x):
    for i in range(M):
        T[(i*10 + x) % M] += S[i]
    for i in range(M):
        T[i] %= MOD

zeros = [0]*M
for c in X:
    T[:] = zeros
    if c == "?":
        for x in range(10):
            calc(S, T, x)
    else:
        x = int(c)
        calc(S, T, x)
    S, T = T, S
print(S[5])

### FIXED CODE ###

X = input()
MOD = 10**9 + 7
M = 13
S = [0]*M
S[0] = 1
T = [0]*M

def calc(S, T, x):
    for i in range(M):
        T[(i*10 + x) % M] += S[i]
    for i in range(M):
        T[i] %= MOD

zeros = [0]*M
for c in X:
    T[:] = zeros
    if c == "?":
        for x in range(10):
            calc(S, T, x)
    else:
        x = int(c)
        calc(S, T, x)
    S, T = T, S
print(S[5])
### BUGGY CODE ###

N,K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
dp = [10**10]*(N+1)
dp[1] = 0
dp[2] = abs(h[0] - h[1])

for i in range(3,N+1):
  Kl = max(1,i-K)
  #print(Kl,i-K,i)
  fr = [dp[j]+abs(h[j-1] - h[i-1]) for j in range(Kl,i)]
  #print(fr)
  dp[i] = min(fr)
print(dp[N])

### FIXED CODE ###

N,K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
dp = [10**10]*(N+1)
dp[1] = 0
dp[2] = abs(h[0] - h[1])

for i in range(3,N+1):
  Kl = max(1,i-K)
  dp[i] = min([dp[j]+abs(h[j-1] - h[i-1]) for j in range(Kl, i)])
print(dp[N])
### BUGGY CODE ###

import sys
import numpy as np
from scipy.misc import comb
sys.setrecursionlimit(1000000)
 
n = int(input())

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

color = [[-1] for i in range(n+1)]

max_j = 0
for i in range(n):
    for j in range(n):
        #print(color[j][-1])
        if a[i] > color[j][-1]:
            color[j].append(a[i])
            max_j = max(max_j,j+1)
            break
            
print(max_j)

### FIXED CODE ###

import sys
input = sys.stdin.readline

from collections import deque

import bisect
n = int(input())

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

#color = [a[0]]

d = deque()
d.appendleft(a[0])

for i in range(1,n):
    idx = bisect.bisect_left(d,a[i])
    if idx == 0:
        d.appendleft(a[i])
    else:
        d[idx-1] = a[i]
        
print(len(d))
### BUGGY CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0]*(M+1) for i in range(N+1)]

for i in range(N):
  for j in range(M):
    if S[i] == T[j]:
      dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] + 1) % MOD
    else:
      dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j]) % MOD

print((dp[N][M] + 1) % MOD)

### FIXED CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0]*(M+1) for i in range(N+1)]

for i in range(N):
  for j in range(M):
    if S[i] == T[j]:
      dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] + 1) % MOD
    else:
      dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j]) % MOD

print((dp[N][M] + 1) % MOD)
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    n = int(input())
    a = list(map(int,input().split()))
    s = set(a)
    cnt = 0
    from collections import Counter
    c = Counter(a)
    for i in range(n):
        if c[a[i]] > 1:
            continue
        tmp = set(make_divisors(a[i]))
        if len(tmp) - len(tmp-s) == 1:
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))
    ans = set(a)
    ma = max(a)
    from collections import Counter
    c = Counter(a)
    for i in range(n):
        t = a[i]
        if c[t] > 1 and t in ans:
            ans.remove(t)
            continue
        j = 2
        tmp = t*j
        while tmp <= ma:
            if tmp in ans:
                ans.remove(tmp)
            j += 1
            tmp = t*j
    print(len(ans))

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

#B
N = int(input())
A = list(sorted(map(int,input().split())))
ans=1
for i in A:
    ans*=i
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

#B
N = int(input())
A = list(sorted(map(int,input().split())))
ans=1
if A[0]==0:
    print(0)
else:
    for i in A:
        ans*=i
        if ans > 10**18:
            ans =-1
            break
    print(ans)
### BUGGY CODE ###

from collections import deque
N=int(input())
tree=[[] for _ in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    tree[u-1].append([v-1,w])
    tree[v - 1].append([u - 1, w])
#print(tree)
col=[-1]*N
dist=[-1]*N
v=0
d=deque()
d.append(v)
color=0
col[0]=0
dist[0]=0
while min(dist)==-1:
    v=d.popleft()
    for i in tree[v]:
        if dist[i[0]]==-1:
            #print(dist[i[0]],dist[v],i[1])
            dist[i[0]]=dist[v]+i[1]
            d.append(i[0])
    #print(dist,d)
    #input()
for i in range(N):
    print(dist[i]%2)

### FIXED CODE ###

from collections import deque
N=int(input())
tree=[[] for _ in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    tree[u-1].append([v-1,w])
    tree[v - 1].append([u - 1, w])
#print(tree)
dist=[-1]*N
v=0
d=deque()
d.append(v)
dist[0]=0
determined=[0]
while len(determined)<N:
    v=d.popleft()
    for i in tree[v]:
        if dist[i[0]]==-1:
            #print(dist[i[0]],dist[v],i[1])
            dist[i[0]]=dist[v]+i[1]
            d.append(i[0])
            determined.append(i[0])
    #print(dist,d,determined)
    #input()
for i in range(N):
    print(dist[i]%2)
### BUGGY CODE ###

# problem D

S = input()
Q = int(input())

query = []
for i in range(0,Q):
    query.append(input().split())

s = S
    
for i in query:
    if int(i[0]) == 1:
        # s を反転させる
        s = s[::-1]
    else:
        if int(i[1]) == 1:
            # 先頭に i[2] をくっつける
            s = str(i[2]) + s
        else:
            # しっぽに i[2] をくっつける
            s = s + str(i[2])

print(s)

### FIXED CODE ###

from collections import deque

s = deque(input())
Q = int(input())
    
t = True
    
for i in range(Q):
    query = input().split()
    if query[0] == '1':
        t = not t
    else:
        if(t and query[1] == '1') or (not t and query[1] == '2'):
            s.appendleft(query[2])
        else:
            s.append(query[2])
            
s = ''.join(s)
    
if not t:
    s = s[::-1]
        
print(s)
### BUGGY CODE ###

import itertools
n = int(input())
sl = []
for i in range(n):
    name = input()
    if name[0] in ['M','A','R','C','H']:
        sl.append(name)
if len(sl) < 3:
    print(0)
    exit()

dic = {'M':0,'A':1,'R':2,'C':3,'H':4}

cnt = 0
for com in itertools.combinations(sl,3):
    lst = [0]*5
    for name in com:
        if lst[dic[name[0]]] == 0:
            lst[dic[name[0]]] += 1
    if sum(lst) == 3:
       cnt += 1
print(cnt)



### FIXED CODE ###

import itertools
n = int(input())
sl = []

dic = {'M':0,'A':0,'R':0,'C':0,'H':0}
for i in range(n):
    name = input()
    if name[0] in dic:
        dic[name[0]] += 1

lst = []
for com in itertools.combinations(dic.keys(),3):
    lst.append(com)

ans = 0
for v in lst:
    ans += dic[v[0]] * dic[v[1]] * dic[v[2]]
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
ls = [0 for _ in range(N)]
flg = 1
for i in range(M):
    a,b = map(int,input().split())
    if ls[a-1] == 0 and ls[b-1] == 0:
        ls[a-1]=flg
        ls[b-1]=flg
        flg+=1
    elif ls[a-1] == 0:
        ls[a-1] = ls[b-1]
    elif ls[b-1] == 0:
        ls[b-1] = ls[a-1]
    else:
        check = ls[b-1]
        ls[b-1] = ls[a-1]
        for l in range(len(ls)):
            if ls[l] == check:
                ls[l]=ls[a-1]
import collections
c = collections.Counter(ls)
plan = c.most_common()
ans = 0
if plan[0][0] == 0 and M != 0:
    ans = plan[1][1]
elif M ==0:
    ans =1
else:
    ans = plan[0][1]
print(ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m = map(int,input().split())
uf = UnionFind(n)
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1)
ans = 0
for j in range(n):
    check = uf.size(j)
    if ans < check:
        ans = check
print(ans)
### BUGGY CODE ###

n, p = map(int, input().split())
ps = []
for i in range(n):
    ps.append(input().split())
    ps[i][1] = int(ps[i][1])
t = 0
i = 0
j = 0
while j < n:
    if ps[i][1] > p:
        ps[i][1] -= p
        t += p
    elif ps[i][1] != 0:
        t += ps[i][1]
        ps[i][1] = 0
        print("{0} {1}".format(ps[i][0], t))
        j += 1
    i = (i + 1) % n


### FIXED CODE ###

n, p = map(int, input().split())
ps = []
for i in range(n):
    ps.append(input().split())
    ps[i][1] = int(ps[i][1])
t = 0
while len(ps) > 0:
    if ps[0][1] > p:
        ps.append([ps[0][0], ps[0][1] - p])
        t += p
        ps.pop(0)
    else:
        t += ps[0][1]
        print("{0} {1}".format(ps[0][0], t))
        ps.pop(0)
### BUGGY CODE ###

n=int(input())
g=[[] for i in range(n)]
ab=[list(map(int,input().split())) for _ in range(n-1)]
for i in range(n-1):
	ab[i][0], ab[i][1] = ab[i][0]-1, ab[i][1]-1
	g[ab[i][0]].append(ab[i][1])
	g[ab[i][1]].append(ab[i][0])

ans=[[0 for i in range(n)]for j in range(n)]
from collections import deque

q=deque()
q.append(0)
num=[0]*n
num[0]=12345678
ma=1
while(q):
	node = q.pop()
	iro=1
	for next in g[node]:
		if num[next]!=0:
			continue
		if iro == num[node]:
			iro+=1
		ans[node][next] = iro
		ans[next][node] = iro
		num[next]=iro
		ma=max(ma,iro)
		q.append(next)
		iro+=1

print(ma)
for i in range(n-1):
	print(ans[ab[i][0]][ab[i][1]])


### FIXED CODE ###

from queue import deque

n=int(input())
ab = [list(map(int,input().split()))for i in range(n-1)]
g = [[]for i in range(n)]
for i,j in ab:
    g[i-1].append(j-1)
ans = {}
banColor = [-1]*n

q = deque([])
q.append(0)
ma = 0

while q:
    nord = q.popleft()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[(nord,value)]= idx + offset
        banColor[value] = idx+offset
        q.append(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i,j in ab:
    print(ans[(i-1,j-1)]+1)
### BUGGY CODE ###

from collections import Counter
N = int(input())
S = [input() for i in range(N)]
C = Counter(S)
M = [kv[0] for kv in C.items() if kv[1] == max(C.values())]
M.sort()
for i in range(len(M)):
    print(M[i])

### FIXED CODE ###

from collections import Counter
N = int(input())
S = [input() for i in range(N)]
C = Counter(S)
freq = max(C.values())
M = [kv[0] for kv in C.items() if kv[1] == freq]
M.sort()
A = '\n'.join(M)
print(A)
### BUGGY CODE ###

input()
S = input()
cnt = 0
for i in range(0, 1000):
  c = [i//100, (i//10)%10, i%10]
  f = 0
  for s in S:
    if int(s) == c[f]:f += 1
    if f==3:break 
  if f==3:cnt += 1
print(cnt)
    

### FIXED CODE ###

input()
S = [int(i) for i in input()]
cnt = 0
for i in range(0, 1000):
  c = (i//100, (i//10)%10, i%10)
  f = 0
  for s in S:
    if s == c[f]:
      f += 1 
      if f==3:break 
  if f==3:cnt += 1
print(cnt)
### BUGGY CODE ###


n = int(input())
a = list(map(int, input().split()))
s = 0
for i in range(len(a)-1):
  s_tmp = sum(a[i+1:len(a)])
  s += a[i] * s_tmp
print(s % 1000000007)



### FIXED CODE ###

n = int(input())
s = 0
a = list(map(int, input().split()))
sum_tmp = sum(a[1:len(a)])
for i in range(len(a)-1):
  s += a[i] * sum_tmp
  sum_tmp -= a[i + 1]
print(s % 1000000007)
### BUGGY CODE ###

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

maxinum = max(nums)
for i in range(N):
    if nums[i] == maxinum:
        print(max(nums[0:i] + nums[i+1:]))
    else:
        print(maxinum)

### FIXED CODE ###

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

maxinum = max(nums)
maxinum2 = -1
for i in range(N):
    if nums[i] == maxinum:
        if maxinum2 == -1:
            maxinum2 = max(nums[0:i] + nums[i+1:])
        print(maxinum2)
    else:
        print(maxinum)
### BUGGY CODE ###

S = input()

while len(S) > 0:
  if "dreameraser" in S:
    S = S.replace("dreameraser","")
  elif "dreamer" in S:
    S = S.replace("dreamer","")
  elif "dream" in S:
    S = S.replace("dream","")
  elif "eraseer" in S:
    S = S.replace("eraser","")
  elif "erase" in S:
    S = S.replace("erase","")
  else:
    break
    
if len(S) == 0:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

S = input()
 
while len(S) > 0:
  if "dreameraser" in S:
    S = S.replace("dreameraser","")
  elif "dreamerase" in S:
    S = S.replace("dreamerase","")
  elif "dreamer" in S:
    S = S.replace("dreamer","")
  elif "dream" in S:
    S = S.replace("dream","")
  elif "eraser" in S:
    S = S.replace("eraser","")
  elif "erase" in S:
    S = S.replace("erase","")
  else:
    break
    
if len(S) == 0:
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

def main3():
    N = int(input())
    S = input()

    R = list()
    G = list()
    B = list()

    for i in range(len(S)):
        if S[i] == "R":
            R.append(i)
        elif S[i] == "G":
            G.append(i)
        elif S[i] == "B":
            B.append(i)

    ans = 0
    for i in R:
        for j in G:
            for k in B:
                li = sorted([i, j, k])
                a, b, c = li[0], li[1], li[2]

                if abs(a - b) != abs(b - c):
                    ans += 1
    print(ans)

if __name__ == "__main__":
    main3()

### FIXED CODE ###

def main4():
    N = int(input())
    S = input()

    R = set()
    G = set()
    B = set()

    for i in range(len(S)):
        if   S[i] == "R":
            R.add(i)
        elif S[i] == "G":
            G.add(i)
        elif S[i] == "B":
            B.add(i)

    ans = 0
    for r in R:
        for g in G:
            a, b = sorted([r, g])
            tmp = len(B)

            if ((b + a) % 2 == 0) and ((b + a) // 2) in B:
                tmp -= 1

            if (2*a - b) in B:
                tmp -= 1

            if (2*b - a) in B:
                tmp -= 1

            ans += tmp
                
    print(ans)

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

def calc_expected_value(n):
    sum_n = [i for i in range(1, n+1)]
    return sum(sum_n) / n


n, k_range = map(int, input().split())
p = list(map(int, input().split()))
e_list = [0] * n
ans_list = [0] * n
ans = 0.0

for i in range(n):
    if i < k_range-1:
        e_list[i] = calc_expected_value(p[i])
    elif i == k_range-1:
        e_list[i] = calc_expected_value(p[i])
        ans_list[i] = sum([e_list[i-k] for k in range(k_range)])
    else:
        e_list[i] = calc_expected_value(p[i])
        # ans = max(ans, sum([e_list[i-k] for k in range(k_range)]))
        ans_list[i] = ans_list[i-1] + e_list[i] - e_list[i-k_range]

print(max(ans_list))

### FIXED CODE ###

def calc_expected_value(n):
    return (n+1) / 2


n, k_range = map(int, input().split())
p = list(map(int, input().split()))
e_list = [0] * n
ans_list = [0] * n
ans = 0.0

for i in range(n):
    e_list[i] = calc_expected_value(p[i])
    if i == k_range-1:
        ans_list[i] = sum([e_list[i-k] for k in range(k_range)])
    else:
        ans_list[i] = ans_list[i-1] + e_list[i] - e_list[i-k_range]

print(max(ans_list))
### BUGGY CODE ###

A,B,N=list(map(int,input().split()))
list_ans=[]
minimum=min(N-3,0)
for i in range(minimum,N+1):
  list_ans.append(int(A*i/B)-A*int(i/B))
print(int(max(list_ans)))

### FIXED CODE ###

A,B,N=list(map(int,input().split()))
list_ans=[]
minimum=min(B-1,N)
print(int(A*minimum/B)-A*int(minimum/B))
### BUGGY CODE ###

#2019の倍数は
Next = [i*10 % 2019 for i in range(2019)]
S = input()
DP = [[0 for j in range(2019)]for i in range(len(S))]#DP[l][d] l桁目(0-index)まで見た時に、余りがdであるような数
ans = 0
for l,s in enumerate(S):
    n = int(s)
    DP[l][n] += 1
    for am,d in enumerate(DP[l-1]):
        DP[l][(10*am + n) % 2019] += d
    ans += DP[l][0]
print(ans)

### FIXED CODE ###

from collections import Counter
Next = [i*10 % 2019 for i in range(2019)]
S = input()
L = list(reversed(S))
Amaris = []#「右から」x桁まで見た場合の余り
amari = 0
kurai = 1
for l in L:
    amari += kurai*int(l)
    amari %= 2019 
    kurai *= 10
    kurai %= 2019
    Amaris.append(amari)
C = Counter(Amaris)
ans = 0 
for d in C.values():
    ans += d*(d-1)//2
print(ans + C[0])
### BUGGY CODE ###

mod=10**9+7
fact=[1]
for i in range(1,5*10**5+1):
  fact.append((fact[-1]*i)%mod)
revfact=[1]
for i in range(1,5*10**5+1):
  revfact.append(pow(fact[i],mod-2,mod))
n,m=map(int,input().split())
patternA=(fact[m]*revfact[n]*revfact[m-n]*fact[n])%mod
patternB=0
for i in range(n+1):
  tmp=(fact[n]*revfact[i]*revfact[n-i])*(fact[m-i]*revfact[n-i]*revfact[m-n])*fact[n-i]
  if i%2==0:
    patternB+=tmp
    patternB%=mod
  else:
    patternB-=tmp
    patternB%=mod
print((patternA*patternB)%mod)

### FIXED CODE ###

mod=10**9+7
fact=[1]
for i in range(1,5*10**5+1):
  fact.append((fact[-1]*i)%mod)
revfact=[1]
for i in range(1,5*10**5+1):
  revfact.append(pow(fact[i],mod-2,mod))
n,m=map(int,input().split())
patternA=(fact[m]*revfact[n]*revfact[m-n]*fact[n])%mod
patternB=patternA
for i in range(1,n+1):
  tmp=(fact[n]*revfact[i]*revfact[n-i])*(fact[m-i]*revfact[n-i]*revfact[m-n])*fact[n-i]
  if i%2==0:
    patternB+=tmp
    patternB%=mod
  else:
    patternB-=tmp
    patternB%=mod
print((patternA*patternB)%mod)
### BUGGY CODE ###

A = int(input())
B = int(input())
C = int(input())
X = int(input())

import itertools
print(len([c for c in set(map(tuple, itertools.chain.from_iterable(itertools.combinations(itertools.chain(itertools.repeat(500, A), itertools.repeat(100, B), itertools.repeat(50, C)), r) for r in range(A + B + C + 1)))) if sum(c) == X]))

### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
X = int(input())

import itertools
print(len([total for total in map(sum, itertools.product(
    [500 * i for i in range(A + 1)],
    [100 * i for i in range(B + 1)],
    [50 * i for i in range(C + 1)],
)) if total == X]))
### BUGGY CODE ###

n=int(input())
a=tuple(list(map(int,input().split())))
s=0
for i in range(n-1):
    for j in range(i+1,n):
        s += (a[i]^a[j])%(10**9+7)
print(s%(10**9+7))

### FIXED CODE ###

import numpy as np

n = int(input())
A = np.array([int(i) for i in input().split()])
ans = 0
#print(A & 1)

# A_iは60ビットまで与えられる.
for i in range(60):
    #A&1は配列Aを1ビット目を表示する: [1,2,3]→[1,0,1]
    c = np.count_nonzero(A & 1) #配列Aの1ビット目が非ゼロのものをカウント
    #cは桁数nを超えないのでn-c>=0
    # c*(n-c)は(0の個数)*(1の個数)を表す.
    ans += 2**i*c*(n-c) #bit毎に計算したのち2**iをかけて10進数に戻す.
    # Aを1ビット右シフト
    A >>= 1 #一つ上の桁数でも同様. 大きな位では0なので値として出てこない.
print(ans%(10**9+7))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in a[:n-1]:
    j = sum(a[a.index(i)+1:])
    ans = (ans+i*j)%(pow(10,9)+7)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
r = sum(a)
for i in a[:n-1]:
    r = r - i
    ans = (ans+i*r)%(10**9+7)
print(ans)