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

S = list(input())
S.reverse()
N = len(S)
mod = 10**9+7

ans = [[0 for r in range(13)] for n in range(N)]
if S[0] == '?':
    for r in range(10):
        ans[0][r] = 1
else:
    ans[0][int(S[0])] = 1
for n in range(1, N):
    if S[n] == '?':
        for r in range(13):
            count = 0
            for d in range(10):
                r1 = d * (10 ** n) % 13
                r0 = (r - r1) % 13
                count += ans[n - 1][r0]
            ans[n][r] = count % mod
    else:
        for r in range(13):
            d = int(S[n])
            r1 = d * (10 ** n) % 13
            r0 = (r - r1) % 13
            ans[n][r] = ans[n-1][r0] % mod
print(ans[N-1][5])


### FIXED CODE ###

S = list(input())
S.reverse()
N = len(S)
mod = 10**9+7
dp = [[0 for r in range(13)] for n in range(N+1)]
dp[0][0] = 1
lookup = [[0 for d in range(10)] for n in range(N)]
for n in range(N):
    for d in range(10):
        lookup[n][d] = d*pow(10, n, 13) % 13
for n in range(1, N+1):
    if S[n-1] == '?':
        for d in range(10):
            for r in range(13):
                dp[n][(r+lookup[n-1][d]) % 13] += dp[n-1][r] % mod
    else:
        for r in range(13):
            dp[n][(r+lookup[n-1][int(S[n-1])]) % 13] += dp[n-1][r] % mod
print(dp[-1][5] % mod)
### BUGGY CODE ###

D = int(1e9 + 7)
N = int(input())
M = [int(i) % D for i in input().split()]

sum_ = 0
for i, x in enumerate(M[:-1]):
    S = M[i+1:]
    sum_ += (sum(S) % D) * x
    sum_ %= D

print(sum_)


### FIXED CODE ###

D = int(1e9 + 7)
N = int(input())
M = [int(i) for i in input().split()]

R = sum(M[1:])

sum_ = 0
for i, x in enumerate(M[:-1]):
    sum_ += R * x
    sum_ %= D
    R -= M[i+1]

print(sum_)
### BUGGY CODE ###

n,m = map(int,input().split())
answers = [i for i in range(1,n+1)]
for i in range(m):
    l,r = map(int,input().split())
    for ans in answers[:]:
        if ans < l or ans > r:
            answers.remove(ans)
print(len(answers))


### FIXED CODE ###

n,m = map(int,input().split())
gates = [list(map(int,input().split())) for _ in range(m)]
l = []
r = []
for gate in gates:
    l.append(gate[0])
    r.append(gate[1])
ans = min(r)+1 - max(l)
print(ans if ans > 0 else 0)
### BUGGY CODE ###

n=int(input())
x=input()
t=int(x,2)
c=x.count('1')
m=[0]*n
k=1
while k<n: m[k]=1; k*=2
def popcount(x):
  x = x - ((x >> 1) & 0x5555555555555555)
  x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
  x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
  x = x + (x >> 8)
  x = x + (x >> 16)
  x = x + (x >> 32)
  return x & 0x0000007f
def f(x):
  if x==0: return 0
  if m[x]: return m[x]
  return f(x%popcount(x))+1
for i in range(n):
  if int(x[i]):
    d=c-1
    if d<1: print(0)
    else: print(f((t-pow(2,n-i-1,d))%d)+1)
  else:
    d=c+1
    print(f((t+pow(2,n-i-1,d))%d)+1)

### FIXED CODE ###

n=int(input())
x=input()
t=int(x,2)
c=x.count('1')
a=t%-~c
b=0 if c<2 else t%~-c
for i in range(n):
  if int(x[i]):
    if c<2: print(0); continue
    else: t=(b-pow(2,n-i-1,c-1))%~-c
  else: t=(a+pow(2,n-i-1,c+1))%-~c
  z=1
  while t:
    d=bin(t).count('1')
    t%=d
    z+=1
  print(z)
### BUGGY CODE ###

S = str(input())

n = len(S)
dp = [[0 for x in range(13)] for _ in range(n + 1)]
dp[0][0] = 1

for i in range(n):
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]
    for j in range(13):
        dp[i + 1][j] %= 10**9 + 7

print(dp[n][5])

### FIXED CODE ###

S = str(input())

ans = [0] * 13
ans[0] = 1
MOD = 10**9 + 7

for i in S:
    dp = [0] * 13
    for j in range(13):
        dp[(j * 10) % 13] = ans[j] % MOD
    dp += dp
    if i == '?':
        for j in range(13):
            ans[j] = sum(dp[j+4:j+14])
    else:
        for j in range(13):
            ans[j] = dp[j + 13 - int(i)]

print(ans[5] % MOD)
### BUGGY CODE ###

from collections import defaultdict, deque

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1

maze = []
for _ in range(H):
    row = list(input())
    maze.append(row)

def dfs(i, j, cnt):
    mapped[i][j] = cnt

    for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        x = i + dx
        y = j + dy
        if 0 <= x < H and 0 <= y < W and maze[x][y] == "." and mapped[x][y] == -1:
            dfs(x, y, cnt)
        elif 0 <= x < H and 0 <= y < W and maze[x][y] == "#" and (i, j) not in edges[cnt]:
            edges[cnt].add((i, j))
            

cnt = 0
mapped = [[-1] * W for _ in range(H)]
edges = defaultdict(set)
for i in range(H):
    for j in range(W):
        if maze[i][j] == "." and mapped[i][j] == -1:
            dfs(i, j, cnt)
            cnt += 1

invalid_pos = set([(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)])
# edges からワープで移動できる島を繋いで、グラフを作る
g = defaultdict(set)
for num in edges:
    for i, j in edges[num]:
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if (dx, dy) in  invalid_pos: continue
                x = i + dx
                y = j + dy
                if 0 <= x < H and 0 <= y < W and mapped[x][y] != -1 and mapped[x][y] != num and mapped[x][y] not in g[num]:
                    g[num].add(mapped[x][y])
                    g[mapped[x][y]].add(num)

# gでのstart, endの最短距離をbfsで求める
start = mapped[ch][cw]
end = mapped[dh][dw]
q = deque([(start, 0),])
seen = set()

isFind = False
while q:
    size = len(q)
    for _ in range(size):
        node, d = q.popleft()
        seen.add(node)
        if node == end:
            print(d)
            isFind = True
            break
        for adj in g[node]:
            if adj not in seen:
                q.append((adj, d+1))
    if isFind:
        break

if not isFind:
    print(-1)



### FIXED CODE ###

from collections import defaultdict, deque

def main():
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1
    maze = [input() for _ in range(H)]

    INF = 10**12
    path = [[INF] * W for _ in range(H)] # 各マスへの移動コスト
    
    # walk:移動A, warp:移動B
    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    q = deque()
    path[ch][cw] = 0
    q.append((ch, cw, 0))

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk: #移動A
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == "." and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s)) # なぜleft?

        for dx, dy in warp: #移動B
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == "." and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s+1)) # なぜright?

    ans = path[dh][dw] if path[dh][dw] != INF else "-1"
    print(ans)

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

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

c = 0
for i in range(N):
  for j in range(i+1, N):
    for k in range(j+1, N):
      if L[k]<L[i]+L[j]:
        c += 1
      
      else:
        break

print(c)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()
 
c = 0
for i in range(N-2):
  for j in range(i+1, N-1):
    c += bisect.bisect_right(L, L[i]+L[j]-1) - j - 1


print(c)
### BUGGY CODE ###

s = list(input())
count = 0
while len(set(s)) == 2:
    for i in range(len(s)):
        if (s[i] == '0' and s[i+1]== '1') or (s[i] == '1' and s[i+1]== '0'):
            s.pop(i)
            s.pop(i)
            count += 2
            break
print(count)

### FIXED CODE ###

s = input()
print(min(s.count('1'), s.count('0'))*2)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))

s1=1
for i in range(k):
    s1*=a[i]

s2=1
for i in range(n-k):
    s2=s1*a[i+k]//a[i]
    if s2>s1:
        print("Yes")
    else:
        print("No")
    s1=s2

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))

for i in range(n-k):
    if a[i]<a[i+k]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from math import gcd
N = int(input())
ans = 0
for i in range(1,N+1):
  for k in range(1,N+1):
    for l in range(1,N+1):
      if i == k and k == l:
        tmp = i
      elif i==k:
        tmp = gcd(k,l)
      elif k==l:
        tmp = gcd(l,i)
      elif l==i:
        tmp = gcd(i,k)

      else:
        a = l 
        b = k
        c = i
        d = gcd(a,b)
        e = gcd(b,c)
        tmp = gcd(d,e)
      ans += tmp

print(ans)


### FIXED CODE ###

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

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

import collections
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = list(input())
    vals = set([])
    for i in range(N):
        vals.add(collections.Counter(S[0:i])["W"] + collections.Counter(S[i+1:])["E"])
    print(min(vals))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = list(input())
    e_right = collections.Counter(S)["E"]
    w_left = 0
    vals = set([])
    for i in range(N):
        if S[i] == "E":
            e_right -= 1
        vals.add(w_left + e_right)
        if S[i] == "W":
            w_left += 1

    print(min(vals))

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

# D - Sum of Divisors
def main():
    N = int(input())
    res = 0
    for a in range(1, N + 1):
        for b in range(1, N // a + 1):
            res += a * b
    print(res)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# D - Sum of Divisors
def main():
    N = int(input())
    res = 0
    for a in range(1, N + 1):
        for b in range(1, N // a + 1):
            res += a * b
    print(res)


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


n = int(input())
str = []
for i in range(n):
    str.append(''.join(sorted(input())))

count = 0
for i in range(len(str)):
    for j in range(i+1, len(str)):
        if str[i] == str[j]:
            count += 1

print(count)

### FIXED CODE ###


import collections
import math

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

n = int(input())
str = []
for i in range(n):
    str.append(''.join(sorted(input())))

c = collections.Counter(str)

count = 0
for k, v in c.items():
    if v > 1:
        count += combinations_count(v, 2)

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

n, q=map(int, input().split())
s=list(input())
l_list=[]
r_list=[]

for i in range(q):
    l, r=map(int, input().split())
    l_list.append(l)
    r_list.append(r)


for i in range(q):
    count=0
    target_s=s[l_list[i]-1:r_list[i]]
    indexes=[i for i, x in enumerate(target_s) if x=="A"]
    for j in indexes:
        if j+1<=len(target_s)-1 and target_s[j+1]=="C":
            count=count+1

    print(count)


### FIXED CODE ###

n, q=map(int, input().split())
s=input()
l_list=[]
r_list=[]

t=[0]*(n+1)
for i in range(n):
    t[i+1]=t[i]+(1 if s[i:i+2]=="AC" else 0)

for i in range(q):
    l, r=map(int, input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

import fractions

K = int(input())
result = 0
sum = 0

for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            result = fractions.gcd(a, b)
            result = fractions.gcd(result, c)
            sum = sum + result

print(sum)  

### FIXED CODE ###

K = int(input())
import math
sum=0
for i in range(1, K+1):
    for j in range(1, K+1):
        value = math.gcd(i,j)
        for k in range(1, K+1):
            sum += math.gcd(value,k)
 
print(sum)
### BUGGY CODE ###

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

here = 1
log = [1]
i = K
while i > 0:
    if i >= 2:
        here = A[here - 1]
        log.append(here)
        here = A[here - 1]

        if here in log:
            loopuntil = log.index(here)
            mod = len(log[loopuntil:])
            i = (K - loopuntil) % mod
            log = []


        else:
            log.append(here)
            i = i - 2

    if i == 1:
        here = A[here - 1]
        i = 0

print(here)

### FIXED CODE ###

N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

now = 1
path = [1]

for i in range(N + 2):
    now = A[now]
    path.append(now)

if i >= K:
    print(path[K])
    quit()

now = path.pop()
lo_start = i - 1
while path[lo_start] != now:
    lo_start -= 1

loop = path[lo_start:]

ans = loop[(K - path.index(now)) % len(loop)]

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

import sys
input = sys.stdin.readline

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

mod = 10 ** 9 + 7

fac = [1]
for i in range(1, N + 1) :
  fac.append(fac[-1] * i)

inv = [pow(fac[-1], mod - 2, mod)]
for i in range(N, 0, -1) :
  inv.append(inv[-1] * i % mod)
inv = inv[::-1]

def comb(n, r) :
  return fac[n] * inv[n-r] * inv[r] % mod

pattern = [1] * N
subtree = [0] * N

# DFS
stack = [(0, -1, 0)]
while stack :
  cur, pre, op = stack.pop()
  
  if op == 0 :
    stack.append((cur, pre, 1))
    for nex in vec[cur] :
      if nex == pre : continue
      stack.append((nex, cur, 0))
  else :
    for nex in vec[cur] :
      pattern[cur] *= pattern[nex] * comb(subtree[cur] + subtree[nex], subtree[nex]) % mod
      pattern[cur] %= mod
      subtree[cur] += subtree[nex]
    subtree[cur] += 1

# BFS
q = [(0, -1)]
while q :
  cur, pre = q.pop()
  for nex in vec[cur] :
    if nex == pre : continue
    pattern[nex] = pattern[cur] * subtree[nex] * inv[N - subtree[nex]] * fac[N - subtree[nex] - 1] % mod
    q.append((nex, cur))
  
for i in range(N) :
  print(pattern[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

mod = 10 ** 9 + 7

fac = [1]
for i in range(1, N + 1) :
  fac.append(fac[-1] * i % mod)

inv = [pow(fac[-1], mod - 2, mod)]
for i in range(N, 0, -1) :
  inv.append(inv[-1] * i % mod)
inv = inv[::-1]

def comb(n, r) :
  return fac[n] * inv[n-r] * inv[r] % mod

pattern = [1] * N
subtree = [0] * N

# DFS
stack = [(0, -1, 0)]
while stack :
  cur, pre, op = stack.pop()
  
  if op == 0 :
    stack.append((cur, pre, 1))
    for nex in vec[cur] :
      if nex == pre : continue
      stack.append((nex, cur, 0))
  else :
    for nex in vec[cur] :
      pattern[cur] *= pattern[nex] * comb(subtree[cur] + subtree[nex], subtree[nex]) % mod
      pattern[cur] %= mod
      subtree[cur] += subtree[nex]
    subtree[cur] += 1

# BFS
queue = [(0, -1)]
while queue :
  cur, pre = queue.pop()
  for nex in vec[cur] :
    if nex == pre : continue
    pattern[nex] = pattern[cur] * subtree[nex] * inv[N - subtree[nex]] * fac[N - subtree[nex] - 1] % mod
    queue.append((nex, cur))
  
for i in range(N) :
  print(pattern[i])
### BUGGY CODE ###

a, b, x = map(int, input().split())
cnt = 0
for i in range(a, b + 1):
    if i % x == 0:
        cnt += 1
print(cnt)

### FIXED CODE ###

a, b, x = map(int, input().split())
cnt = b // x
cnt -= (a - 1) // x
print(cnt)
### BUGGY CODE ###

# ABC137C

n = int(input())
s = [0] * n
for i in range(n):
    s[i] = input()
s = [sorted(list(t)) for t in s]
count = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        count += s[i] == s[j]
print(count)


### FIXED CODE ###

from math import factorial

def unique(w):
    d = {}
    for c in w:
        if c in d.keys():
            d[c] += 1
        else:
            d.setdefault(c, 1)
    return list(d.values())

n = int(input())
s = [0] * n
for i in range(n):
    s[i] = input()
# s = sorted([''.join(sorted(list(t))) for t in s])
s = [''.join(sorted(list(t))) for t in s]
values = unique(s)
count = 0
for i in values:
    if i > 1:
        count += factorial(i) // factorial(2) // factorial(i - 2)
print(count)
### BUGGY CODE ###

def mapint_inp():
    return map(int, input().split())

def intinp():
    return int(input())

N = intinp()
A = list(mapint_inp())

lim = 10**18
ans = 1
f = True
for A_i in A:
    ans = ans*A_i
    if 0 in A:
        ans = 0
        break
    if ans > lim:
        f = False
        break

if f:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

def mapint_inp():
    return map(int, input().split())

def intinp():
    return int(input())

N = intinp()
A = list(mapint_inp())

lim = 10**18
ans = 1
f = True
if 0 in A:
    ans = 0
else:
    for A_i in A:
        ans = ans*A_i
        if ans > lim:
            f = False
            break

if f:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

A,B,K=map(int,input().split())
while(K!=0):
	K-=1
	if A>=1:
		A-=1
	elif B>=1:
		B-=1
	elif A==B:
		break
print(A,B)

### FIXED CODE ###

a, b, k = map(int, input().split())
 
if a >= k:
    print(a - k, b)
else:
    print(0, max(0, b - k + a))
### BUGGY CODE ###

class UnionFind():

    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for i in range(n)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

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

        if (x == y):
            return
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

    def sizeOfGroup(self, x):
        return len(self.memsInGroup(x))


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

road = UnionFind(N)
train = UnionFind(N)

for i in range(K):
    p, q = map(int, input().split())
    road.unite(p-1, q-1)

for j in range(L):
    r, s = map(int, input().split())
    train.unite(r-1, s-1)

for i in range(N):
    conByRoad = road.memsInGroup(i)
    conByTrain = train.memsInGroup(i)

    ans = len(set(conByRoad) & set(conByTrain))
    print(ans)


### FIXED CODE ###

from collections import Counter
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for i in range(n)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if (root_x == root_y):
            return
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x

        elif self.rank[root_y] > self.rank[root_x]:
            self.parent[root_x] = root_y

        else:
            self.parent[root_x] = root_y
            self.rank[root_y] += 1

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

    def memsInGroup(self, x):
        """
        O(N)かかります
        """
        root = self.find(x)
        return [i for i in range(N) if root == self.find(i)]

    def sizeOfGroup(self, x):
        return len(self.memsInGroup(x))

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

road = UnionFind(N)
train = UnionFind(N)

for i in range(K):
    p, q = map(int, input().split())
    road.unite(p-1, q-1)

for j in range(L):
    r, s = map(int, input().split())
    train.unite(r-1, s-1)

pair = [(road.find(i), train.find(i)) for i in range(N)]
# print(pair)
c = Counter(pair)
# print(c)
ans = [c[i] for i in pair]
# print(ans)
print(*ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, K: int):
    dictionary = {} # key k番目には、kを最小公倍数として持つような組合せの数が保存されている。
    for k in range(K, 0, -1):
        dictionary[k] = (int(K / k) ** N)
        multiplier = 2
        while k * multiplier <= K:
            dictionary[k] -= dictionary[k * multiplier]
            multiplier += 1

    result = sum([k * v for k, v in dictionary.items()])
    print(result % (10**9+7))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, K: int):
    num_gcd = {}
    for k in range(K, 0, -1):
        num_select = K // k
        num_gcd_k = pow(num_select, N, MOD)
        for multiple in range(2, num_select+1):
            num_gcd_k -= num_gcd[k * multiple]
        num_gcd[k] = num_gcd_k

    result = 0
    for k in range(1, K+1):
        result += (k * num_gcd[k]) % MOD
    print(result % MOD)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)

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

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
    
b = []

for i in range(len(a)):
    if a[i] in b:
        b.remove(a[i])
    else:
        b.append(a[i])
        
print(len(b))

### FIXED CODE ###

n = int(input())

nlll = {}
    
for i in range(n):
    aaa = int(input())
    if aaa in nlll:
        del nlll[aaa]
    else:
        nlll.update({aaa:1})

sums = 0
for i in nlll.values():
    sums = sums + i
print(sums)
### BUGGY CODE ###

# coding: utf-8
n, q = map(int, input().split())
s = input()

for i in range(q):
    l, r = map(int, input().split())
    moji = s[l-1:r]
    print(moji.count('AC'))

### FIXED CODE ###

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

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

    mod = 10**9 + 7
    answer = 0

    for i in range(0, n-1):
        sum_other = sum(a[i+1:])
        if sum_other >= mod:
            answer %= mod
        answer += a[i] * sum_other
        if answer >= mod:
            answer %= mod

    print(answer)


'''
    for i in range(n):
        sum_sub = 0
        for j in range(i+1, n):
            sum_sub += a[j]
            if sum_sub >= mod:
                sum_sub %= mod
        answer += a[i] * sum_sub
        if answer >= mod:
            answer %= mod
    print(answer)
'''

'''
    for i in range(n):
        for j in range(i+1, n):
            answer += a[i] * a[j]
            if answer >= mod:
                answer %= mod
    print(answer)
'''

if __name__ == "__main__":
    main()


### FIXED CODE ###

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

    mod = 10**9 + 7
    answer = 0
    sum_a = sum(a) % mod

    for i in range(n):
        sum_a = sum_a - a[i]
        answer += a[i] * sum_a
        answer %= mod

    print(answer)


'''
    for i in range(n):
        sum_sub = 0
        for j in range(i+1, n):
            sum_sub += a[j]
            if sum_sub >= mod:
                sum_sub %= mod
        answer += a[i] * sum_sub
        if answer >= mod:
            answer %= mod
    print(answer)
'''

'''
    for i in range(n):
        for j in range(i+1, n):
            answer += a[i] * a[j]
            if answer >= mod:
                answer %= mod
    print(answer)
'''

if __name__ == "__main__":
    main()