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

import sys
sys.setrecursionlimit(100000)

n = int(input())
s = input()
s_set = set(s)
S = []
for i in s_set:
    S.append(s.count(i))

def cal(n, S):
    if n == 1:
        return sum(S)
    if n == 2:
        ans = 0
        for i in range(len(S) - 1):
            for j in range(i+1, len(S)):
                ans += S[i] * S[j]
            ans %= 10 ** 9 + 7
        return ans
    else:
        ans = 0
        for i in range(len(S) - n + 1):
            ans += S[i] * cal(n-1, S[i+1:])
            #ans %= 10 ** 9 +7
        return ans

ans = 0
for i in range(n):
    ans += cal(i+1, S)

ans %= 10 ** 9 + 7
print(ans)



### FIXED CODE ###

n = int(input())
s = input()
s_set = set(s)
S = []
for i in s_set:
    S.append(s.count(i))

ans = 1
for i in S:
    ans *= i + 1
    ans %= 10 ** 9 + 7

print(ans - 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
h = list(map(int, input().split()))
init = (10 ** 4) * N
dp = [init] * N
dp[0] = 0
 
for i in range(1, N):
    min = init
    for j in range(1, K+1):
        if i - j < 0:
            break
        tmp = dp[i-j] + abs(h[i] - h[i-j])
        if tmp < min:
            min = tmp
    dp[i] = min
     
print(dp[N-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
h = [int(x) for x in input().split()]
dp = [0] * N

for i, hi in enumerate(h):
    if i == 0:
        continue
    if i - K < 0:
        dp[i] = min(dpk + abs(hi-hk) for dpk, hk in zip(dp[:i], h[:i]))
    else:
        dp[i] = min(dpk + abs(hi-hk) for dpk, hk in zip(dp[i-K:i], h[i-K:i]))

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

n=int(input())
a=list((input().split()))
b=[]
for i in range(n):
    b.append(a[i])
    b=b[::-1]
print(' '.join(b))

### FIXED CODE ###

from collections import deque
n=int(input())
a=list(map(int,input().split()))
b=deque([])
for i in range(n):
    if i%2==0:
        b.appendleft(a[i])
    else:
        b.append(a[i])

if n%2==0:
    b=list(b)[::-1]

print(*b)
### BUGGY CODE ###

h, w = input().split()
h = int(h)
w = int(w)

n = input()
n = int(n)

an = input().split()
an = [int(a) for a in an]

field = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
    for j in range(w):
        if i % 2 != 0:
            j = -j - 1
        for k in range(n):
            if an[k] > 0:
                an[k] -= 1
                field[i][j] = k+1
                break

for i in range(h):
    output = [str(c) for c in field[i]]
    print(" ".join(output))



### FIXED CODE ###

h, w = input().split()
h = int(h)
w = int(w)

n = input()
n = int(n)

an = input().split()
an = [int(a) for a in an]

field = [[0 for _ in range(w)] for _ in range(h)]

k = 0
for i in range(h):
    for j in range(w):
        if i % 2 != 0:
            j = -j - 1
        if an[k] > 0:
            pass
        else:
            k += 1
        an[k] -= 1
        field[i][j] = k+1

for i in range(h):
    output = [str(c) for c in field[i]]
    print(" ".join(output))
### BUGGY CODE ###

n=int(input())
xd=[list(map(int,input().split())) for _ in range(n)]
xd.sort(key=lambda x:x[0])
aryx=[x for x,d in xd]
mod=998244353
dp=[1]*(n+1)
#dp[n-1]=2
r=list(range(n))
r[n-1]=n-1
from bisect import bisect_left
for i in range(n):
    x,d=xd[n-1-i]
    tmp=bisect_left(aryx,x+d)
    ri=max(r[n-1-i:tmp])
    r[n-1-i]=ri
    dp[n-1-i]=dp[n-1-i+1]+dp[ri+1]
    dp[n-1-i]%=mod
print(dp[0])


### FIXED CODE ###

n=int(input())
xd=[list(map(int,input().split())) for _ in range(n)]
xd.sort(key=lambda x:x[0])
aryx=[x for x,d in xd]
mod=998244353
dp=[1]*(n+1)
#dp[n-1]=2
r=list(range(n))
r[n-1]=n-1
from bisect import bisect_left

class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : max(x,y), default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res
st=SegmentTree(n)
for i in range(n):
    st.update(i,i)

for i in range(n):
    x,d=xd[n-1-i]
    tmp=bisect_left(aryx,x+d)
    sti=st.query(n-1-i,tmp)
    st.update(n-1-i,sti)
    dp[n-1-i]=dp[n-1-i+1]+dp[sti+1]
    dp[n-1-i]%=mod
print(dp[0])
### BUGGY CODE ###

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

import bisect
A = []
for _ in range(N):
    bisect.insort_left(A, tuple(int(x) for x in input().split()))

acc = 0
for x in A:
    a, b = x
    acc += b
    if acc >= K:
        print(a)
        break

### FIXED CODE ###

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

from heapq import *
q = []
for _ in range(N):
    heappush(q, tuple(int(x) for x in input().split()))

acc = 0
while q:
    a, b = heappop(q)
    acc += b
    if acc >= K:
        print(a)
        break
### BUGGY CODE ###

from itertools import product
import numpy as np

N,M = list(map(int,input().split()))
A = np.array(input().split(),dtype='int64')

C = np.append([0],np.cumsum(A))   
L =[1 for t, i in product(C,C) if i<t and (t - i)%M==0]


print(len(L))

### FIXED CODE ###

import collections
import numpy as np

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

A = np.array(A,dtype='int64')
C = np.append([0],np.cumsum(A))
L = [i%M for i in C]
L_c = collections.Counter(L)

ans = 0
for i in L_c.values():
    S = i * (i-1) / 2
    ans+=S
    
print(int(ans))
### BUGGY CODE ###

a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())

sa = abs(a - b)
sas = abs(v - w)
if w >= v:
    print("NO")
    exit(0)

for i in range(t):
    sa -= sas
if sa <= 0:
    print("YES")
else:
    print("NO")



### FIXED CODE ###

a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())

sa = abs(a - b)
sas = abs(v - w)
if w >= v:
    print("NO")
    exit(0)

d = sa // sas

if d >t:
    print("NO")
if d == t:
    if sa % sas == 0:
        print("YES")
    else:
        print("NO")
if d < t:
    if sa - (d*sas) -sas <=0:
        print("YES")
    else:
        print("NO")
### BUGGY CODE ###

k, s = map(int, input().split())

xyz = [s, 0, 0]

count = 0

def cal(lis, n):
    lis[n] = lis[n] - 1
    lis[n+1] = lis[n+1] + 1

while xyz[0] >= 0:
    xyzCopy = list(xyz)
    while xyzCopy[1] >= 0:
        if xyzCopy[0] <= k and xyzCopy[1] <= k and xyzCopy[2] <= k:
            count = count + 1
        cal(xyzCopy, 1)
    cal(xyz, 0)

print(count)

### FIXED CODE ###

k, s = map(int, input().split())

count = 0

for i in range(k+1):
    for j in range(k+1):
        if 0 <= s-i-j <= k:
            count = count + 1

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

import sys

limit = 1E18
n = int(input())
total = 1
# A string
line = str(input())
for i in line.split():
    x = int(i)
    total *= x

print(-1 if total > limit else total)

### FIXED CODE ###

limit = 1E18
n = int(input())
total = 1
# A string
line = str(input())

if line.startswith("0 ") or " 0" in line:
    print(0)
    exit()

for i in line.split():
    x = int(i)
    total *= x
    if total > limit:
        print(-1)
        exit()

print(-1 if total > limit else total)
### BUGGY CODE ###

s = list(input())
n = len(s)
a_count = 0
ans = 0
i = 0
while i < n-2:
    if s[i:i+3] == ['A','B','C']:
        ans +=  1
        s[i+2] = 'A'
        s[i+1] = 'C'
        s[i] = 'B'
        i -= 2
    i += 1
print(ans)

### FIXED CODE ###

s = input()
n = len(s)
s = list(s.replace('BC','D'))
a_count = 0
ans = 0
i = 0
while i < len(s) - 1 :
    if s[i:i+2] == ['A','D']:
        ans += a_count + 1
        s[i+1] = 'A'
        s[i] = 'D'
    else:
        if s[i] == 'A':
            a_count += 1
        else:
            a_count = 0
    i += 1
print(ans)
### BUGGY CODE ###

N, *A = map(int, open(0).read().split())

A = sorted(enumerate(A), reverse=True, key=lambda x: x[1])

dp = [[0] * (N + 1) for _ in range(N + 1)]
for i, (p, a) in enumerate(A):
    for j in range(i + 1):
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + a * (p - j))
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a * (N - (i - j) - 1 - p))

print(max(dp[N]))

### FIXED CODE ###

N, *A = map(int, open(0).read().split())

A = sorted(enumerate(A), reverse=True, key=lambda x: x[1])

dp = [[0] * (N + 1) for _ in range(N + 1)]
for i, (p, a) in enumerate(A):
    for j in range(i + 1):
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + a * (p - j))
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a * (N - (i - j) - 1 - p))

print(max(dp[N]))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
 
    l, r = [int(i) for i in input().split()]
    
    minmod = float('inf')

    for i in range(l, r):
        for j in range(i+1, r+1):
            temp = (i*j)%2019
            if(temp < minmod):
                minmod = temp
 
            #print("i = {}, j = {}, temp = {}, minmod = {}".format(i, j, temp, minmod))
 
    print(minmod)
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
 
    l, r = [int(i) for i in input().split()]
 
    if(r - l) >= 2019:
        print(0)
        exit()
    
    minmod = float('inf')
 
    for i in range(l, r):
        for j in range(i+1, r+1):
            temp = (i*j)%2019
            if(temp < minmod):
                minmod = temp
 
            #print("i = {}, j = {}, temp = {}, minmod = {}".format(i, j, temp, minmod))
 
    print(minmod)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n,m = map(int, input().split())
t = [[] for i in range(n)]
dis = [n for i in range(n)]
dis[0] = 0
near = [0 for i in range(n)]
c = []
for i in range(m):
    a,b = map(int, input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)
for i in range(len(t[0])):
    dis[t[0][i]] = 1
    near[t[0][i]] = 0
    c.append(t[0][i])
while len(c) > 0:
    d = len(c)
    for i in range(d):
        e = c[0]
        for j in range(len(t[e])):
            if dis[t[e][j]] >= dis[e] +1:
                 dis[t[e][j]] = dis[e] +1
                 near[t[e][j]] = e
                 c.append(t[e][j])
        del c[0]
if max(dis) == n:
    print('No')
else:
    print('Yes')
    for i in range(1,len(near)):
        print(near[i]+1)


### FIXED CODE ###

from collections import deque
n,m = map(int, input().split())
t = [[] for i in range(n)]
near = [-1 for i in range(n)]
near[0] = 0
q = deque()
for i in range(m):
    a,b = map(int, input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)
for i in range(len(t[0])):
    c = t[0][i]
    near[c] = 0
    q.append(c)
while len(q) > 0:
    e = q.popleft()
    for j in range(len(t[e])):
        c = t[e][j]
        if near[c] == -1:
            near[c] = e
            q.append(c)
print('Yes')
for i in range(1,len(near)):
    print(near[i]+1)
### BUGGY CODE ###

def gijkstra(n,E,key=1,s=1):
    T, Q = [[float('inf'), -1] for i in range(n+1)], list(range(1,n+1))
    T[s][0] = 0
    Q.sort(key=lambda x:-T[x][0])
    while Q:
        u = Q.pop()
        for e in E[u]:
            v = e[0]
            d = T[u][0] + e[key]
            if T[v][0] > d:
                T[v] = [d, u]
                Q.sort(key=lambda x:-T[x][0])
    return T

n, m, s, t =  map(int,input().split())
E = [[] for i in range(n+1)]
for i in range(m):
    e = tuple(map(int,input().split()))
    E[e[0]].append(e[1:2]+e[2:])
    E[e[1]].append(e[0:1]+e[2:])
T1 = gijkstra(n,E,key=1,s=s)
T2 = gijkstra(n,E,key=2,s=t)
T = [T1[v][0]+T2[v][0] for v in range(n+1)]
for i in range(n):
    print(10**15 - min(T[i+1:]))

### FIXED CODE ###

import heapq
from collections import defaultdict
def gijkstra(n,E,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in E[u]:
            if d[v] > d[u] + c:
                d[v], p[v] = d[u]+c, u
                heapq.heappush(hq, (d[u]+c, v))
    return d, p

n, m, s, t =  map(int,input().split())
E1 = defaultdict(set)
E2 = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E1[u].add((v,a))
    E1[v].add((u,a))
    E2[u].add((v,b))
    E2[v].add((u,b))
d1, _ = gijkstra(n,E1,s=s)
d2, _ = gijkstra(n,E2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d.append(min(d[-1],d1[i]+d2[i]))
[print(10**15-c) for c in reversed(d)]
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 1
if n == 2:
  print(max(a))
else:
  a0 = a[0]
  a1 = a[1]
  r = 0
  while True:
    r = a1 % a0
    if r == 0:
      b0 = a0
      break
    elif r > a0:
      a1, a0 = r, a0
    else:
      a1, a0 = a0, r
  a1 = a[1]
  a2 = a[2]
  r = 0
  while True:
    r = a2 % a1
    if r == 0:
      b1 = a1
      break
    elif r > a1:
      a2, a1 = r, a1
    else:
      a2, a1 = a1, r
  a0 = a[0]
  a2 = a[2]
  r = 0
  while True:
    r = a2 % a0
    if r == 0:
      b2 = a0
      break
    elif r > a0:
      a2, a0 = r, a0
    else:
      a2, a0 = a0, r
  max_a = max(b0,b1,b2)
  kouho = []
  for j in range(max_a,1,-1):
    if max_a % j == 0:
      kouho.append(j)
  for j in kouho:
    c = list(map(lambda x: x % j,a))
    c_ng = [i for i in c if i > 0]
    #print("j=",j,"c=",c,"c_ng=",c_ng)
    if len(c_ng) <= 1:
      ans = j
      break
  print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 1
if n == 2:
  print(max(a))
else:
  a0 = a[0]
  a1 = a[1]
  r = 0
  while True:
    r = a1 % a0
    if r == 0:
      b0 = a0
      break
    elif r > a0:
      a1, a0 = r, a0
    else:
      a1, a0 = a0, r
  a1 = a[1]
  a2 = a[2]
  r = 0
  while True:
    r = a2 % a1
    if r == 0:
      b1 = a1
      break
    elif r > a1:
      a2, a1 = r, a1
    else:
      a2, a1 = a1, r
  a0 = a[0]
  a2 = a[2]
  r = 0
  while True:
    r = a2 % a0
    if r == 0:
      b2 = a0
      break
    elif r > a0:
      a2, a0 = r, a0
    else:
      a2, a0 = a0, r
  max_a = max(b0,b1,b2)
  kouho = []
  for j in range(max_a,1,-1):
    if max_a % j == 0:
      c = list(map(lambda x: x % j,a))
      c_ng = [i for i in c if i > 0]
    #print("j=",j,"c=",c,"c_ng=",c_ng)
      if len(c_ng) <= 1:
        ans = j
        break
  print(ans)
### BUGGY CODE ###

import sys


def main():
    N = int(input())
    #P = tuple(map(int, input().split()))
    P = (map(int, input().split()))

    Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

    Sitting = [1] * (N * N)
    Kcount = 0


    #def Kcheck(qsn, cdsn):
    #    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
    #        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
    #        queue.append(cdsn)


    for sn in P:
        csn = sn - 1
        Kcount += Kcost[csn]
        Sitting[csn] = 0
        queue = [csn]

        while queue:
            qsn = queue.pop()
            div, mod = divmod(qsn, N)
            if mod: #Kcheck(qsn, qsn - 1)
                cdsn = qsn - 1
                if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
                    Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
                    queue.append(cdsn)
            if mod != N - 1: #Kcheck(qsn, qsn + 1)
                cdsn = qsn + 1
                if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
                    Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
                    queue.append(cdsn)
            if div: #Kcheck(qsn, qsn - N)
                cdsn = qsn - N
                if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
                    Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
                    queue.append(cdsn)
            if div != N - 1: #Kcheck(qsn, qsn + N)
                cdsn = qsn + N
                if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
                    Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
                    queue.append(cdsn)

    print(Kcount)


if __name__ == '__main__':
    main()

sys.exit()


### FIXED CODE ###

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

Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

Sitting = [1] * (N * N)
Kcount = 0


def Kcheck(qsn, cdsn):
    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
        queue.append(cdsn)


for sn in P:
    csn = sn - 1
    Kcount += Kcost[csn]
    Sitting[csn] = 0
    queue = [csn]

    while queue:
        qsn = queue.pop()
        div, mod = divmod(qsn, N)
        if mod: Kcheck(qsn, qsn - 1)
        if mod != N - 1: Kcheck(qsn, qsn + 1)
        if div: Kcheck(qsn, qsn - N)
        if div != N - 1: Kcheck(qsn, qsn + N)

print(Kcount)
### BUGGY CODE ###


n=int(input())
a = list(map(int, input().split()))
an=0
for i in range(n-1):
    s=a[i]
    for j in range(s+i+1,n):
        if j-i==a[j]+s:
            an+=1
print(an)

### FIXED CODE ###

import collections
n=int(input())
a = list(map(int, input().split()))
an=0
ii=[]
jj=[]
for i in range(n):
    ii.append(i+a[i])
    jj.append(i-a[i])
jjj=collections.Counter(jj)
for i in range(n):
    an+=jjj[ii[i]]
print(an)
### BUGGY CODE ###

temp = input()
temp2 = temp.split(" ")
temp = []
for i in temp2:
    temp.append(int(i))

for i in range(1,100000000):
    ans1 = temp[0]*i
    if ans1 % temp[1] != 0:
        break
print(ans1)
    

### FIXED CODE ###

temp = input()
temp2 = temp.split(" ")
temp = []
for i in temp2:
    temp.append(int(i))

for i in range(1,100000000):
    ans1 = temp[0]*i
    if ans1 % temp[1] != 0:
        break
    if ans1 >= 10^18:
        ans1 = -1
        break
print(ans1)
### BUGGY CODE ###

import itertools
n,k = map(int,input().split())
p = [int(i) for i in input().split()]
ans = []

combi = list(itertools.combinations(p,k))
for i in range(len(combi)) :
    ans.append(sum(combi[i]))
print(min(ans))

### FIXED CODE ###

n,k = map(int,input().split())
p = [int(i) for i in input().split()]
p.sort()
s = 0
for i in range(k) :
    s += p[i]
print(s)
### BUGGY CODE ###

def calc():
 n=int(input())
 table=[0]*(n+1)
 for i in range(1,n+1): #各iについて、iの倍数の約数の個数table[i*j]を1増やす
   for j in range(i,n+1,i):
     table[j]+=1
 ans=0
 for i in range(1,n+1):
   ans+=i*table[i] #すべてのKについてf(K)を求められたので答えを計算する
 print(ans)
calc()

### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1): #各iについて、i*(1～n//iまでの総和)を足し合わせればよい
 k=n//i
 ans+=i*(k*(k+1)//2)
print(ans)
### BUGGY CODE ###

def main():
    s = input()
    K = int(input())
    alp = 'abcdefghijklmnopqrstuvwxyz'
    sk = []
    for a in alp:
        for i in range(len(s)):
            c = s[i]
            if a != c:
                continue
            for j in range(1, K + 1):
                ss = s[i:i + j]
                if ss not in sk:
                    sk.append(ss)
    print(sorted(sk)[K - 1])


main()


### FIXED CODE ###

def main():
    s = input()
    K = int(input())
    sk = []
    for i in range(len(s)):
        for j in range(1, K + 1):
            ss = s[i:i + j]
            if ss not in sk:
                sk.append(ss)
    print(sorted(sk)[K - 1])


main()
### BUGGY CODE ###

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

A = []
A.append(list('@'*(W+2)))
for i in range(H):
  a = list('@'+input()+'@')
  A.append(a)
A.append(list('@'*(W+2)))

vy = [0,0,1,-1]
vx = [1,-1,0,0]
b_count = 0
ans = 0
while(1):
 b_count = 0
 tmp_list = []
 for i in range(H+2):
  if((i != 0)and(i != H+1)):
   for j in range(W+2):
    if((j != 0)and(j != W+1)):
     if(A[i][j] == '#'): 
       tmp_list.append([i,j])
       b_count += 1
 
 #終了条件
 if(b_count == H*W):
  break
  
 for i in range(len(tmp_list)):
  tmp_y,tmp_x = tmp_list[i][0],tmp_list[i][1]
  for j in range(4):
    if(A[tmp_y+vy[j]][tmp_x+vx[j]] == '.'):
      A[tmp_y+vy[j]][tmp_x+vx[j]] = '#'
 
 ans += 1
 
print(ans)      
  

### FIXED CODE ###

from collections import deque

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

by,bx= deque(),deque()
Map = []
Map.append('@'*(W+2))
for i in range(H):
  c = list('@'+input()+'@')
  Map.append(c)
  for j in range(W+2):
    if(c[j] == '#'):
      Map[i+1][j] = 0
      by.append(i+1),bx.append(j)
Map.append('@'*(W+2))      

cnt = 0
while(1):
  if(len(by) == 0):
    break
   
  ny,nx = by.popleft(),bx.popleft()
  vec_y,vec_x = [1,-1,0,0],[0,0,1,-1]
  for i in range(4):
      if(Map[ny+vec_y[i]][nx+vec_x[i]] == '.'):
         Map[ny+vec_y[i]][nx+vec_x[i]] = Map[ny][nx] + 1
         cnt = max(cnt, Map[ny][nx] + 1) 
         by.append(ny+vec_y[i]),bx.append(nx+vec_x[i])
  
print(cnt)
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
f = [r,g,b]
f.sort()
r,g,b = f[2],f[1],f[0]

ans = 0
R = 0

while 1:
     G = 0
     if R*r>n:
          break
     while 1:
          if R*r+G*g>n:
               break
          if (n-R*r-G*g)%b == 0:
               ans += 1
          G += 1
     R += 1
     
print(ans)

### FIXED CODE ###

r,g,b,n = map(int,input().split())
f = [r,g,b]
f.sort()
r,g,b = f[2],f[1],f[0]

ans = 0
R = 0

while 1:
     G = 0
     if R*r>n:
          break
     while 1:
          if R*r+G*g>n:
               break
          if (n-R*r-G*g)%b == 0:
               ans += 1
          G += 1
     R += 1
     
print(ans)
### BUGGY CODE ###

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

A = [[] for _ in range(H)]
Aset = [[] for _ in range(H)]
for i in range(H):
    A[i] = list(map(int,input().split()))
    Aset[i] = set(A[i])

#1,1+D,1+2D,...
#2,2+D,2+2D,...
#...
#D,2D,3D,...
cost = [0]*(H*W+1)
for i in range(1,D+1):
    num = i
    now = None#座標
    while True:
        if num > H*W:
            break
        for row in range(H):
            if num in Aset[row]:
                #print(row)
                ind = A[row].index(num)
                if now == None:
                    now = (ind, row)#x,y
                    cost[num] = 0
                else:
                    cost[num] = cost[num-D] + abs(ind-now[0]) + abs(row-now[1])
                    now = (ind, row)
        num += D

Q = int(input())
for _ in range(Q):
    l, r = map(int,input().split())
    print(cost[r]-cost[l])

### FIXED CODE ###

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

A = [[] for _ in range(H)]
Aset = [[] for _ in range(H)]
for i in range(H):
    A[i] = list(map(int,input().split()))
    Aset[i] = set(A[i])

#1,1+D,1+2D,...
#2,2+D,2+2D,...
#...
#D,2D,3D,...
cost = [0]*(H*W+1)
for i in range(1,D+1):
    num = i
    now = None#座標
    while True:
        if num > H*W:
            break
        for row in range(H):
            if num in Aset[row]:
                #print(row)
                ind = A[row].index(num)
                if now == None:
                    now = (ind, row)#x,y
                    cost[num] = 0
                else:
                    cost[num] = cost[num-D] + abs(ind-now[0]) + abs(row-now[1])
                    now = (ind, row)
        num += D

Q = int(input())
for _ in range(Q):
    l, r = map(int,input().split())
    print(cost[r]-cost[l])
### BUGGY CODE ###

import itertools

N = int(input())
A = [int(n) for n in input().split()]
ans = 0
m = 1000000007

for x, y in itertools.combinations(A, 2):
    ans += x * y

print(ans % m)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
m = 1000000007

s = 0
for i in range(N):
    ans += A[i] * s
    s += A[i]

print(ans % m)