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

import sys,math,copy
input = sys.stdin.readline
S = input().strip()
N = len(S)

dp = [[0] * 13 for _ in range(N+1)]
dp[0] = [1] * 13
mod = 1
if S[-1] == '?':
    for d in range(10):
        dp[1][(d * mod) % 13] = 1
else:
    dp[1][(int(S[-1]) * mod) % 13] = 1

S = S[0:N-1]
for n, s in enumerate(S[::-1], start=2):
    mod = (mod * 10) % 13
    if s == '?':
        for d in range(10):
            m = (d * mod) % 13
            for pm in range(13):
                dp[n][(pm+m)%13] += dp[n-1][pm]
    else:
        m = (int(s) * mod) % 13
        for pm in range(13):
            dp[n][(pm+m)%13] += dp[n-1][pm]

print(dp[-1][5] % (10 ** 9 + 7))

### FIXED CODE ###

import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

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

N = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        ans += A[i] * A[j] % 1000000007
        ans = ans % 1000000007
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
a = 0
b = 0
mod = 10**9 + 7
for i in range(N):
    a += A[i]
    b += A[i]**2
    a = a 
    b = b 
a = a ** 2 
ans = (a - b) // 2 % mod
if ans < 0:
    ans += mod
print(ans)
### BUGGY CODE ###

from numba import jit

@jit
def factor(N):
    arr=[]
    for i in range(1,int(N**0.5)+1):
        if(N%i==0):
            arr.append(i)
            waru.add(i)
            if(N//i!=i):
                arr.append(N//i)
                waru.add(N//i)
    return arr
waru=set()

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

cnt=[0]*1000001
for i in range(N):
    cnt[A[i]]+=1
ng=set()
for i in range(N):
    if cnt[A[i]]>1:
        ng.add(A[i])

s=set(A)

ans=0

for i in range(N):
    if A[i] in ng:
        continue
    s.remove(A[i])
    arr=factor(A[i])
    ok=True
    for x in arr:
        if x in s:
            ok=False
            break
    if ok:
        ans+=1
    s.add(A[i])
print(ans)

### FIXED CODE ###

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

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

cnt=[0]*1000001
for i in range(N):
    cnt[A[i]]+=1
ng=set()
for i in range(N):
    if cnt[A[i]]>1:
        ng.add(A[i])

s=set(A)
min_=min(A)

ans=0
for i in reversed(range(N)):
    if A[i] in ng:
        continue
    if A[i]<min_*2:
        ans+=1
        continue
    s.remove(A[i])
    arr=factor(A[i])
    ok=True
    for x in arr:
        if x in s:
            ok=False
            break
    if ok:
        ans+=1
    s.add(A[i])
print(ans)
### BUGGY CODE ###

K = int(input())
K_list = []
for i in range(1, K+1):
    K_list = [i] + K_list

ans = 0

def gcd(a, b, c):
    for i in K_list:
        if a % i == b % i == c % i == 0:
            return i


for i in range(1, K +1):
    for j in range(1, K+1):
        for t in range(1, K+1):
            ans += gcd(i, j, t)

print(ans)

### FIXED CODE ###

import math
k = int(input())
ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        gcd1 = math.gcd(i,j)
        for t in range(1, k+1):
            ans += math.gcd(gcd1, t)

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

mod = 10**9 + 7
n = int(input())
A = [int(i) for i in input().split()]
for i in range(1,n+1):
	l = 0
	if A.count(i) > 1:
		l = i
		p = []
		for j in range(n+1):
			if A[j] == l:
				p.append(j)
		break
	if l:
		break

t = 1
d = 1
for k in range(n+1):

	t *= (n+1-k)%mod*pow(k+1,mod-2,mod)
	t %= mod
	if not k:
		print(n)
	elif k <= n+p[0]-p[1]:
		d *= (n+p[0]-p[1]-k+1)%mod*pow(k,mod-2,mod)
		d %= mod
		print((t - d)%mod)
	else:
		print(t%mod)



### FIXED CODE ###

from collections import Counter
mod = 10**9 + 7
n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
l = 0
for i in range(1,n+1):
	if C[i] > 1:
		l = i
		p = []
		for j in range(n+1):
			if A[j] == l:
				p.append(j)
				if len(p) > 1:
					break
		break
	if l:
		break

t = 1
d = 1
for k in range(n+1):

	t *= (n+1-k)%mod
	t %= mod
	t *= pow(k+1,mod-2,mod)
	t %= mod
	if not k:
		print(n)
	elif k <= n+p[0]-p[1]:
		d *= (n+p[0]-p[1]-k+1)%mod
		d %= mod
		d *= pow(k,mod-2,mod)
		d %= mod
		print((t - d)%mod)
	else:
		print(t%mod)
### BUGGY CODE ###

import math
a, b, n = map(int, input().split())
arr = []
ans = 0
for i in range(min(b, n)):
  x = i + 1
  arr.append(math.floor(a * x / b) - a * math.floor(x / b))
ans = max(arr)
print(ans)

### FIXED CODE ###

import math
a, b, n = map(int, input().split())
x = min(b - 1, n)
ans = math.floor(a * x / b) - a * math.floor(x / b)
print(ans)
### BUGGY CODE ###

#import sys
import heapq
#import copy
#import numpy as np
from collections import deque

h,w=list(map(int,input().split()))
a=[['.']*w for i in range(h)]
q=deque()
cnt=0
for i in range(h):
    for j,x in enumerate(input()):
        if x=='#':
            deque.append(q,[i,j])
            a[i][j]=0

while len(q)>0:
    hh,ww=deque.popleft(q)

    for nh,nw in [[hh+dh,ww+dw] for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]]:
        
        if 0>nh or nh>=h or 0>nw or nw>=w or a[nh][nw]!='.':
            continue
        
        a[nh][nw]=a[hh][ww]+1
        cnt=max(cnt,a[nh][nw])

        deque.append(q,[nh,nw])

print(cnt)


### FIXED CODE ###

from collections import deque

h,w=list(map(int,input().split()))
a=[[c for c in input()] for _ in range(h)]
visit=[[0]*w for _ in range(h)]
q=deque()

for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            deque.appendleft(q,(i,j,0))
            visit[i][j]=1
ans=0
while len(q)>0:
    i,j,cnt=deque.pop(q)

    ans=max(ans,cnt)

    for di,dj in [(-1,0),(1,0),(0,-1),(0,1)]:
        ni=i+di
        nj=j+dj
        if 0<=ni<h and 0<=nj<w and visit[ni][nj]==0:
            visit[ni][nj]=1
            deque.appendleft(q,(ni,nj,cnt+1))

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

def resolve():
    N = int(input())

    answer = 0

    for A in range(1, N+1):
        A_top = str(A)[0]
        A_least = str(A)[-1]
        for B in range(1, N+1):
            B_top = str(B)[0]
            B_least = str(B)[-1]
            if A_least == B_top and A_top == B_least:
                answer += 1

    print(answer)

 
if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import sys

def preprocessing():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))

    solve(N)

def solve(N: int):
    counts = [[0] * 10 for _ in range(10)]
    for i in range(10, N + 1):
        b = i % 10 
        while i >= 10:
            i //= 10 # Truncated division (i = i // 10)
        counts[i][b] += 1
    ret = 0
    for i in range(1, min(N + 1, 10)):
        ret += 1
        if counts[i][i] > 0:
            ret += counts[i][i] * 2
    for i in range(1, 10):
        for j in range(1, 10):
            ret += counts[i][j] * counts[j][i]
    print(ret)
    return


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

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def gcd(m, n):
  r=m%n
  return gcd(n, r) if r else n
def lcm(m, n):
  return m*n//gcd(m, n)

def main():
  n=I()
  l=LI()

  a=1
  for x in l:
    a=lcm(a,x)

  ans=0
  for x in l:
    ans+=a//x

  return ans%mod

# main()
print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def lcm(a,b): return a*b//fractions.gcd(a,b)

def main():
  n=I()
  l=LI()

  a=1
  for x in l:
    a=lcm(a,x)

  ans=0
  for x in l:
    ans+=a//x

  return ans%mod

# main()
print(main())
### BUGGY CODE ###

inr = lambda: list(map(int, input().split()))
inn = lambda: input()
 
N,Q = inr()
S = inn()
for q in range(Q):
    l,r = inr()
    bubun = S[l-1:r]
    
    bbb = ""
    for b in bubun:
      if b in ["A","C"]:
        bbb += b
    
    print(bbb.count("AC"))

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
pref = [0]
for i in range(1,n):
  if s[i-1:i+1] == "AC": 
      pref.append(pref[-1]+1)
  else: 
      pref.append(pref[-1])
for i in range(q):
    l,r = map(int,input().split())
    print(pref[r-1]-pref[l-1])
### BUGGY CODE ###

from collections import defaultdict

def eratosthenes(N):
	is_prime = [True] * (N + 1)
	is_prime[0], is_prime[1] = False, False
	for i in range(2, int(N**(1/2)) + 1):
		if is_prime[i]:
			for j in range(i * 2, N + 1, i):
				is_prime[j] = False
	return [i for i in range(N+1) if is_prime[i]]

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
primes = eratosthenes(10**6+1)

tot_cnt = defaultdict(lambda: 0)

def factorization(num):
	tmp_cnt = defaultdict(lambda: 0)
	for p in primes:
		if p > num:
			break

		while True:
			if num % p == 0:
				num //= p
				tmp_cnt[p] += 1
			else:
				break

	return tmp_cnt

for a in A:
	T = factorization(a)
	for t in T:
		tot_cnt[t] = max(tot_cnt[t], T[t])

lcm = 1
for t in tot_cnt:
	lcm *= pow(t, tot_cnt[t], mod)
	lcm %= mod

ans = 0
for a in A:
	tmp = lcm * pow(a, mod-2, mod)
	ans += tmp
	ans %= mod

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
def gcd(a,b):
	if b == 0:
		return a
	return gcd(b, a%b)
LCM = A[0]
for i in range(1, N):
	GCD = gcd(LCM, A[i])
	LCM *= A[i]
	LCM //= GCD
LCM %= mod
ans = 0
for i in range(N):
	t = LCM * pow(A[i], mod-2, mod)
	ans += t
	ans %= mod

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

n = int(input())
a = list(map(int,input().split()))
for i in range(1,n+1):
    print(a.count(i))

### FIXED CODE ###

from collections import Counter
n = int(input())
a = Counter(list(map(int,input().split())))
for i in range(1,n+1):
    print(a[i])
### BUGGY CODE ###

from collections import deque
import sys
inputs = sys.stdin.readline
N,M = map(int,input().split())
UV = [tuple(map(lambda x:int(x)-1,inputs().split())) for i in range(M)]
S,T = map(lambda x:int(x)-1,input().split())

es = [[set() for j in range(N)] for i in range(3)]
for u,v in UV:
    es[0][u].add(v)

for i in range(2):
    for j in range(N):
        for k in es[i][j]:
            es[i+1][j] |= es[0][k]

INF = float('inf')
dist = [INF]*N
dist[S] = 0
q = deque([S])
while q:
    v = q.popleft()
    for to in es[2][v]:
        if dist[to] != INF: continue
        dist[to] = dist[v]+1
        if to == T:
            print(dist[to])
            exit()
        q.append(to)

print(-1)

### FIXED CODE ###

from collections import deque
import sys
inputs = sys.stdin.readline
N,M = map(int,input().split())
UV = [tuple(map(lambda x:int(x)-1,inputs().split())) for i in range(M)]
S,T = map(lambda x:int(x)-1,input().split())

es = [[] for i in range(3*N)]
for u,v in UV:
    es[u].append(v+N)
    es[u+N].append(v+2*N)
    es[u+2*N].append(v)

q = deque([S])
INF = float('inf')
dist = [INF] * (3*N)
dist[S] = 0

while q:
    v = q.popleft()
    for to in es[v]:
        if dist[to] != INF: continue
        dist[to] = dist[v] + 1
        if to==T:
            print(dist[to] // 3)
            exit()
        q.append(to)
print(-1)
### BUGGY CODE ###

count = 0

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

q = []

for i in range(n):
    q.append(p[i])
    if q[i] == min(q):
        count += 1

print(count)

### FIXED CODE ###

count = 0

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

min = 10**7
for i in range(n):
    if p[i] < min:
        count += 1
        min = p[i]

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

n = int(input())
a = [int(i) for i in input().split()]
L, R = [0] * n, [0] * n
for i in range(n):
    L[i] = i + a[i] 
    R[i] = i - a[i] 
def make_dic(L):
    L_set = set(L)
    return dict([(i, L.count(i)) for i in L_set])
L_dic, R_dic = make_dic(L), make_dic(R)
cnt = 0
for Lk, Lv in L_dic.items():
    try:
        cnt += R_dic[Lk] * Lv
    except KeyError:
        pass
print(cnt)

### FIXED CODE ###

n = int(input())
L_dict, R_dict = {}, {}
i = 0
for ipt in input().split():
    try:
        L_dict[i + int(ipt)] += 1
    except KeyError:
        L_dict[i + int(ipt)] = 1
    try:
        R_dict[i - int(ipt)] += 1
    except KeyError:
        R_dict[i - int(ipt)] = 1
    i += 1
cnt = 0
for Lk, Lv in L_dict.items():
    try:
        cnt += R_dict[Lk] * Lv
    except KeyError:
        pass
print(cnt)
### BUGGY CODE ###

import sys


def input(): return sys.stdin.readline().strip()


def solve():
    pass


def main():
    N = int(input())
    I = [x for x in range(1, N+1)]
    P = [x for x in range(1, N+1)]
    P = P[1:] + [P[0]]

    for i in range(N):
        I[i] %= P[i]

    print(sum(I))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    ans = (N-1)*(1+N-1) // 2
    print(ans)


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

def main():
    n = int(input())
    s = []
    ans = 0
    
    for _ in range(n):
        ss = ''.join(sorted(input()))
        s.append(ss)
    
    for i in range(n):
        for j in range(i+1, n):
            if s[i] == s[j]:
                ans += 1
            
    print(ans)
       
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def main():
    n = int(input())
    d = {}
    ans = 0
    
    for _ in range(n):
        ss = ''.join(sorted(input()))
        d[ss] = d.get(ss, 0) + 1
        
    for k, v in d.items():
        if v != 1:
            ans += combinations_count(v, 2)
         
    print(ans)
       
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import copy

n = int(input())
arr = [int(input()) for _ in range(n)]
ans = []

for ele in arr:
    tmp = copy.copy(arr)
    tmp.remove(ele)
    print(max(tmp))


### FIXED CODE ###

n = int(input())
arr = [int(input()) for _ in range(n)]
ar = sorted(arr)
mx = ar[-1]
sc = ar[-2]

for ele in arr:
    if ele == mx:
        print(sc)
    else:
        print(mx)
### BUGGY CODE ###

import bisect
cost = 0
t = raw_input()
W, H = map(int, t.split(' '))
p, q = [], []
for i in xrange(W):
    p.append((i, int(raw_input())))
p.sort(key=lambda a: a[1])
pp = [each[1] for each in p]
cost += sum(pp)
for j in xrange(H):
    new = int(raw_input())
    cost += new
    minus = bisect.bisect_right(pp, new)
    cost += (W-minus) * new
    for k in xrange(minus):
        cost += pp[k]

print cost

### FIXED CODE ###


import bisect
cost = 0
t = raw_input()
W, H = map(int, t.split(' '))
p, q = [], []
sum_p = []
for i in xrange(W):
    tmp = int(raw_input())
    p.append((i, tmp))
p.sort(key=lambda a: a[1])
pp = [each[1] for each in p]
for i in xrange(W):
    if not sum_p:
        sum_p.append(pp[i])
    else:
        sum_p.append(sum_p[-1]+pp[i])
cost += sum(pp)
for j in xrange(H):
    new = int(raw_input())
    cost += new
    minus = bisect.bisect_right(pp, new)
    cost += (W-minus) * new
    cost += sum_p[minus-1] if minus > 0 else 0

print cost
### BUGGY CODE ###

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

cnt = 0
print(len([i for i in range(N) if all([True if P[j] >= P[i] else False for j in range(i)])]))


### FIXED CODE ###

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

cnt = 0
min_value = N + 1
for i in range(N):
    if P[i] <= min_value:
        cnt += 1
        min_value = P[i]
print(cnt)
### BUGGY CODE ###

import numpy as np

n = int(input())
L = np.array(sorted(list(map(int, input().split()))))

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        m = L[j]-L[i]
        M = L[j]+L[i]
        res = L[j+1:]
        res_m = np.where(m < res, 1, 0)
        res_M = np.where(res >= M, 1, 0)
        ans += sum(res_m)-sum(res_M)

print(ans)


### FIXED CODE ###

import bisect

n = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += bisect.bisect_left(L, L[i]+L[j]) - (j+1)

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

x, y, z, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

p = []
for i in range(x):
  for j in range(y):
    for l in range(z):
      if (i+1) * (j+1) * (l+1) <= k:
        p.append(a[i]+b[j]+c[l])

p.sort(reverse=True)

for i in range(k):
  print(p[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

p = []
for i in range(x):
  if i <= k:
    for j in range(y):
      if (i+1) * (j+1) <= k:
        for l in range(z):
          if (i+1) * (j+1) * (l+1) <= k:
            p.append(a[i]+b[j]+c[l])
          else:
            break
      else:
        break
  else:
    break

p.sort(reverse=True)

for i in range(k):
  print(p[i])
### BUGGY CODE ###

N = int(input())
l = list(map(int, input().split()))
sum = 1
for i in l:
    sum *= i
if sum > 1000000000000000000:
    print(-1)
else:
    print(sum)

### FIXED CODE ###

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

ans = 1

for x in range(N):
    ans *= A[x]
    if ans > 10**18:
        ans = -1
        break
        
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

N = int(input())

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

col = [ -1 for i in range(N)]

col[0] = 0

d = {}
for i in range(N+1):
    d[i] = []
d[0].append(0)
p = []
def dfs(n,c,path):
    global p
    path = path + [n]
    if n == N - 1:
        p = path
    for v in e[n]:
        if col[v] == -1:
            col[v] = c + 1
            d[c+1].append((n,v))
            dfs(v,c+1,path)
dfs(0,0,[])
#print(col)
#print(p)

if len(p) % 2 ==0:
    fn = p[len(p)//2-1]
    sn = p[len(p)//2]
else:
    fn = p[len(p)//2]
    sn = p[len(p)//2+1]

#print(fn,sn)

colfn = [ -1 for i in range(N)]
colfn[0] = 0
def dfs2(n,c):

    for v in e[n]:
        if v == sn:
            continue
        elif colfn[v] == -1:
            colfn[v] = c + 1
            dfs2(v,c+1)

dfs2(0,0)
fennec = -1
for i in range(N):
    if colfn[i] != -1:
        fennec += 1
#print(fennec)

colsn = [ -1 for i in range(N)]
colsn[N-1] = 0
def dfs3(n,c):

    for v in e[n]:
        if v == fn:
            continue
        elif colsn[v] == -1:
            colsn[v] = c + 1
            dfs3(v,c+1)

dfs3(N-1,0)
snuke = -1
#print(colsn)
for i in range(N):
    if colsn[i] != -1:
        snuke += 1
#print(snuke)

if fennec > snuke:
    print("Fennec")
else:
    print("Snuke")


### FIXED CODE ###

import sys

p = []
path = [ 0 for i in range(10**5+1)]
def main():

    sys.setrecursionlimit(1000000)

    N = int(input())

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

    col = [ -1 for i in range(N)]
    col[0] = 0
    
    #def dfs(n,c,path):
    def dfs(n,c):
        global p
        #path =  path  + [n]
        #path.append(n)
        #print(path)
        if n == N - 1:
            p = path
        path[c] = n
        for v in e[n]:
            if col[v] == -1:
                col[v] = c + 1
                dfs(v,c+1)
                #dfs(v,c+1,path)
                if p:
                    return
    dfs(0,0)
    #print(p[:N+10])
    #dfs(0,0,[])

    t = col[N-1] + 1
    if t % 2 ==0:
        sn = p[t//2]
    else:
        sn = p[t//2+1]


    colfn = [ -1 for i in range(N)]
    colfn[0] = 0
    def dfs2(n,c):

        for v in e[n]:
            if v == sn:
                continue
            elif colfn[v] == -1:
                colfn[v] = c + 1
                dfs2(v,c+1)

    dfs2(0,0)

    fennec = -1
    for i in range(N):
        if colfn[i] != -1:
            fennec += 1

    snuke = N - fennec - 2
    if fennec > snuke:
        print("Fennec")
    else:
        print("Snuke")



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

import fractions
import itertools
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

n = int(input())
tup = tuple(map(int,input().split()))
max = 0
for i in tuple(itertools.combinations(tup,n-1)):
    l = gcd(*i)
    if max<l:
        max = l
        num = i
print(max)

### FIXED CODE ###

from fractions import gcd

n = int(input())
a = list(map(int,input().split()))
left = [0]*n
right = [0]*n
for i in range(1,n):
    left[i] = gcd(left[i-1],a[i-1])
    right[-1-i] = gcd(right[-i],a[-i])
gcds = []
for i in range(n):
    gcds.append(gcd(left[i],right[i]))
print(max(gcds))
### BUGGY CODE ###

n_y = list(map(int,input().split()))

price = 0
ok = 0

for i in range(n_y[0]+1):
    for j in range(n_y[0]+1):
        for k in range(n_y[0]+1):
            price = 10000 * i + 5000 * j + 1000 * k   
            
            if price == n_y[1] and i+j+k == n_y[0] and ok == 0:
                print(i, j, k)
                ok = 1
                break

            else:
                no_flg = 1
        else:
            continue
        break
    else:
        continue
    break

if no_flg == 1 and ok == 0:
    print(-1, -1, -1 )

### FIXED CODE ###

n,y = map(int,input().split())

price = 0
ok = 0

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

            price = 10000 * i + 5000 * j + 1000 * k   
            
            if price == y and i+j+k == n and ok == 0:
                print(i, j, k)
                ok = 1
                break

    else:
        continue
    break

if ok == 0:
    print(-1, -1, -1 )
### BUGGY CODE ###

n = int(input())
a  = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans += (a[i] * a[j]) % mod
        ans %= mod

print(ans)

### FIXED CODE ###

from itertools import accumulate
n = int(input())
a = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
a_acc = list(accumulate(a))
ans = 0
for i in range(n):
    ans += (a[i] * (a_acc[-1] - a_acc[i])) % mod
    ans %= mod
print(ans)