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

# F - Silver Fox vs Monster

import bisect

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    # sum[0:i+1]
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    # add x to i
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N, D, A = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

X = [XH[i][0] for i in range(N)]
X_right = [bisect.bisect_right(X, XH[i][0] + 2*D) for i in range(N)]

ans = 0
bomb_damage = Bit(N+1)
for i in range(N):
    damage = bomb_damage.sum(i+1)
    if XH[i][1] - damage > 0:
        n_bomb = -(-(XH[i][1] - damage)//A)
        ans += n_bomb
        bomb_damage.add(i+1, n_bomb * A)
        bomb_damage.add(X_right[i]+1, -n_bomb * A)

print(ans)


### FIXED CODE ###

# F - Silver Fox vs Monster

import bisect

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    # sum[0:i+1]
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    # add x to i
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N, D, A = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

X = [XH[i][0] for i in range(N)]
X_right = [bisect.bisect_right(X, XH[i][0] + 2*D) for i in range(N)]

ans = 0
bomb_damage = Bit(N+1)
for i in range(N):
    damage = bomb_damage.sum(i+1)
    if XH[i][1] - damage > 0:
        n_bomb = -(-(XH[i][1] - damage)//A)
        ans += n_bomb
        bomb_damage.add(i+1, n_bomb * A)
        bomb_damage.add(X_right[i]+1, -n_bomb * A)

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

import sys

stdin = sys.stdin

ns = lambda: stdin.readline()
ni = lambda: int(ns())
na = lambda: list(map(int,stdin.readline().split()))

n = ni()
a = na()

ret = []
for i, x in enumerate(a):
    ret.append(x)
    ret.reverse()

ans = ""
for i, x in enumerate(ret):
    ans += str(x)
    if (i!=n-1): ans += " "
    
print (ans)

### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline()
ni = lambda: int(ns())
na = lambda: list(map(int,stdin.readline().split()))

n = ni()
a = na()

l = []
m = []
for i, x in enumerate(a):
    if (i%2==1):
        l.append(x)
    else:
        m.append(x)

if (n%2==0):
    l.reverse()
    l.extend(m)
    ret = l
else:
    m.reverse()
    m.extend(l)
    ret = m

ans = ""
for i, x in enumerate(ret):
    ans += str(x)
    if (i!=n-1): ans += " "
    
print (ans)
### BUGGY CODE ###

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

D = []
count = 0
mode = 1
if S[0] == "0":
    D.append(0)
    mode = 0

for i in range(len(S)):
    if int(S[i]) == mode:
        count += 1
    else:
        D.append(count)
        count = 1
        mode = 1 - mode
    if i == len(S)-1:
        D.append(count)

if S[-1] == "0":
    D.append(0)

lk = int((len(D)-1)/2)
if K > lk:
    K = lk
ans = 0
for i in range(int((len(D)-2*K-1)/2)+1):
    j = 2*i
    k = 2*K + 2*i + 1
    sumd = sum(D[j:k])
    if sumd > ans:
        ans = sumd

print(ans)


### FIXED CODE ###

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

D = []
count = 0
mode = 1
if S[0] == "0":
    D.append(0)
    mode = 0

for i in range(N):
    if int(S[i]) == mode:
        count += 1
    else:
        D.append(count)
        count = 1
        mode = 1 - mode
    if i == N-1:
        D.append(count)

if S[-1] == "0":
    D.append(0)
lk = int((len(D)-1)/2)
if K > lk:
    K = lk
ans = sum(D[:(2*K+1)])
sumd = ans
for i in range(int((len(D)-2*K-1)/2)):
    sumd += D[2*K+2*i+1]+D[2*K+2*i+2]-D[2*i]-D[2*i+1]
    if sumd > ans:
        ans = sumd

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

import numpy as np
h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(map(int, list(input()))))
s = np.array(s)

def count(li):
    hh = len(li)
    tmp = [0]*hh
    cnt = 0
    for i in range(w):
        for j in range(hh):
            if li[j, i]>k:
                return -1
            if tmp[j]+li[j, i]>k:
                cnt += 1
                for x in range(hh):
                    tmp[x] = li[x, i]
                break
            tmp[j] += li[j, i]
    return cnt

ans = 1000000
for i in range(2**(h-1)):
    r = 0
    l = []
    for j in range(h-1):
        if (i>>j)&1:
            l.append(np.sum(s[r:j+1, :], axis=0))
            r = j+1
    l.append(np.sum(s[r:, :], axis=0))
    cnt = count(np.vstack(l))
    if cnt>=0:
        ans = min(ans, cnt+len(l)-1)
print(ans)


### FIXED CODE ###

import numpy as np
h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(map(int, list(input()))))
s = np.array(s)

def count(li):
    if np.max(li) > k:
        return -1
    tmp = np.zeros(len(li), dtype=int)
    cnt = len(li)-1
    for i in range(w):
        tmp += li[:, i]
        if np.max(tmp) > k:
            cnt += 1
            if cnt >= ans:
                return -1
            tmp = li[:, i]
    return cnt

ans = 1000000
for i in range(2**(h-1)):
    r = 0
    l = []
    for j in range(h-1):
        if (i>>j)&1:
            l.append(np.sum(s[r:j+1, :], axis=0))
            r = j+1
    l.append(np.sum(s[r:, :], axis=0))
    if ans <= len(l)-1:
        continue
    cnt = count(np.vstack(l))
    if cnt>=0:
        ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(100000)
N, Q = map(int, input().split())

neighbor = defaultdict(list)
counter = [0] * N
pcounter = [0] * N

for i in range(N-1):
    a, b = map(int, input().split())
    neighbor[a-1].append(b-1)
    neighbor[b-1].append(a-1)
for i in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

def find(x, llist):
    while llist is not None:
        y, llist = llist
        if y == x:
            return True
    return False


stack = [(0, 0, None)]
while stack:
    (node, acc, ancestors) = stack.pop()
    counter[node] += acc
    acc = counter[node]
    ancestors = (node, ancestors)
    for c in neighbor[node]:
        if not find(c, ancestors):
            stack.append((c, acc, ancestors))

print(*counter, sep=' ')


### FIXED CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(100000)
N, Q = map(int, input().split())

neighbor = defaultdict(list)
counter = [0] * N
pcounter = [None] * N
depth = {0: 0}

for i in range(N-1):
    a, b = map(int, input().split())
    a_deper, b_deeper = False, False
    if a in depth and b not in depth:
        depth[b] = depth[a] + 1
    if b in depth and a not in depth:
        depth[a] = depth[b] + 1
    if a in depth and b in depth:
        if depth[a] < depth[b]:
            neighbor[a-1].append(b-1)
        else:
            neighbor[b-1].append(a-1)
    else:
            neighbor[a-1].append(b-1)
            neighbor[b-1].append(a-1)

for i in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

def solve():
    stack = [(0, None)]
    while stack:
        (node, parent) = stack.pop()
        pcounter[node] = counter[node]
        if parent is not None:
            pcounter[node] += pcounter[parent]
        for c in neighbor[node]:
            if pcounter[c] is None:
                stack.append((c, node))

solve()
print(*pcounter, sep=' ')
### BUGGY CODE ###

N = int(input())
s = []
for _ in range(N):
    s.append(''.join(sorted(input().lower())))

l = []
count = 0
for n in range(N):
    if s[n] in l:
        count += l.count(s[n]) 
        l.append(s[n])
    else :
        l.append(s[n])

print(count)

### FIXED CODE ###

N = int(input())
s = []
for _ in range(N):
    s.append(''.join(sorted(input().lower())))

l = {}
for n in range(N):
    if s[n] in l:
        l[s[n]] += 1
    else :
        l[s[n]] = 1

print(sum(l[k] * (l[k]-1) // 2 for k in l))
### BUGGY CODE ###

N = int(input())
A = tuple(map(int, input().split()))
CA = []
cumsum = 0
for a in A:
    cumsum += a
    CA.append(cumsum)

mindiff = CA[-1]
for i in range(0, N-3):
    p = CA[i]
    for j in range(i+1, N-2):
        q =  CA[j] - CA[i]
        for k in range(j+1, N-1):
            r = CA[k] - CA[j]
            s = CA[-1] - CA[k]
            mindiff = min(mindiff, max([p, q, r, s]) - min([p, q, r, s]))
print(mindiff)

### FIXED CODE ###

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

from itertools import accumulate
CA = list(accumulate(A))

mindiff = CA[-1]
left = 0
right = 2
for c in range(1,N-1):
    # left side
    p = CA[left]
    q = CA[c] - CA[left]
    while True:
        pi = CA[left+1]
        qi = CA[c] - CA[left+1]
        if abs(pi- qi) >= abs(p - q):
            break
        p = pi; q = qi
        left += 1

    # right side
    r = CA[right] - CA[c]
    s = CA[-1] - CA[right]
    while True:
        ri = CA[right+1] - CA[c]
        si = CA[-1] - CA[right+1]
        if abs(ri- si) >= abs(r - s):
            break
        r = ri; s = si
        right += 1

    mindiff = min(mindiff, max(p, q, r, s) - min(p, q, r, s))
print(mindiff)
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())
A = np.array(sorted(list(map(int, input().split()))))
BC = []
for _ in range(M):
  bc = list(map(int, input().split()))
  A = np.append(A, [bc[1]] * bc[0])
A = sorted(A, reverse=True)
print(sum(A[:N]))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for _ in range(M):
  BC.append(list(map(int, input().split())))
BC = sorted(BC, key=lambda x:x[1],reverse=True)  
for b, c in BC:
  A.extend([c] * b)
  if len(A)>=2*N:
    break
A = sorted(A, reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

n, m = map(int, input().split(' '))
s = [list(map(int, input().split(' '))) for _ in range(m)]

dic = [x for x in range(n)]
result = [int(n*(n-1)/2)]
for i in range(1,m):
    if dic[s[-1*i][0]-1] == dic[s[-1*i][1]-1]:
        result.append(result[-1])
    else:
#        p = [x for x in dic if x == dic[s[-1*i][0]-1]]
#        q = [x for x in dic if x == dic[s[-1*i][1]-1]]
        p = dic.count(dic[s[-1*i][0]-1])
        q = dic.count(dic[s[-1*i][1]-1])
        result.append(result[-1]-p*q)
        if p<q:
            dic = [dic[s[-1*i][1]-1] if x == dic[s[-1*i][0]-1] else x for x in dic]
        else:
            dic = [dic[s[-1*i][0]-1] if x == dic[s[-1*i][1]-1] else x for x in dic]
for i in range(1,m+1):
    print(result[-1*i])

### FIXED CODE ###

n, m = map(int, input().split(' '))
a = [0]*m
b = [0]*m
for i in range(m):
    a[i], b[i] = list(map(int, input().split(' ')))

c = [-1]*(m+2)

def find(num):
    if c[num] < 0:
        return num
    else:
        k = find(c[num])
        c[num] = k
        return k

result = [int(n*(n-1)/2)]
for i in range(m-1, 0,-1):
    x = find(a[i])
    y = find(b[i])

    if x != y:
        result.append(result[-1]-c[x]*c[y])
        x, y = sorted([x,y])
        c[x] += c[y]
        c[y] = x
    else:
        result.append(result[-1])

for i in result[::-1]:
    print(int(i))
### BUGGY CODE ###

n = int(input())
inputs = [list(map(int,input().split())) for i in range(n-1)]
out = []
for station_st in range(n-1):
    spend_time = inputs[station_st][1]+inputs[station_st][0] #次の駅に着く時間

    for st_num_cur in range(station_st+1,n-1):
        train_leave_time = inputs[st_num_cur][1] 
        train_i = 0
        while(inputs[st_num_cur][1]+inputs[st_num_cur][2]*train_i < spend_time):
            train_i += 1
        train_leave_time = inputs[st_num_cur][1] + inputs[st_num_cur][2]*train_i
        spend_time = train_leave_time+inputs[st_num_cur][0] #次の駅で乗れる電車が出発する時間
    print(spend_time)
print(0)

### FIXED CODE ###

n = int(input())
inputs = [list(map(int,input().split())) for i in range(n-1)]
out = []
for station_st in range(n-1):
    spend_time = inputs[station_st][1]+inputs[station_st][0] #次の駅に着く時間

    for st_num_cur in range(station_st+1,n-1):
        if spend_time < inputs[st_num_cur][1]:
            spend_time = inputs[st_num_cur][1]

        train_leave_time = inputs[st_num_cur][1] 
        train_i = 0
        wait_time = 0
        if (spend_time%inputs[st_num_cur][2])!=0:
            wait_time = inputs[st_num_cur][2] - (spend_time%inputs[st_num_cur][2])
        spend_time += wait_time + inputs[st_num_cur][0] #次の駅で乗れる電車が出発する時間
        #print("spend",wait_time,spend_time)
    print(spend_time)
print(0)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

BC.sort(key=lambda x: x[1], reverse=True)
A.sort()
s = 0
for B, C in BC:
    mn = A[0]
    if mn >= C:
        s += sum(A)
        break
    n = len(A)
    if B > n:
        B = n
    if A[B - 1] <= C:
        s += B * C
        if B == n:
            break
        A = A[B:]
    else:
        a, b = 0, B
        while a + 1 < b:
            i = a + (b - a) // 2
            if A[i] >= C:
                b = i
            else:
                a = i
        s += b * C
        s += sum(A[b:])
        break
else:
    s += sum(A)
print(s)

### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

BC.sort(key=lambda x: x[1], reverse=True)
A.sort()
l, r = 0, N
for B, C in BC:
    if A[l] >= C:
        break
    a, b = l, r
    if A[r - 1] >= C:
        while a + 1 < b:
            i = a + (b - a) // 2
            if A[i] >= C:
                b = i
            else:
                a = i
        r = b
    n = B + l
    if n > r:
        n = r
        B = n - l
    if n <= b:
        A[l:n] = [C] * B
        l = n
    else:
        A[l:b] = [C] * B
        l = b
    if l == r:
        break

print(sum(A))
### BUGGY CODE ###

N = int(input())

print(sum([i+1 for i in range(N-1)]))

### FIXED CODE ###

N = int(input())

print(int((N)*(N-1)//2))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000)

n,q=map(int,input().split())
G=[[] for i in range(n)] #隣接配列
P=[0]*n #根のポイント
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    p-=1
    P[p]+=x
    

def dfs(s,p=-1,cnt=0):
    cnt+=P[s]
    P[s]=cnt
    for i in G[s]:
        if i!=p:
            dfs(i,s,cnt)

dfs(0)
print(*P)

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque

def main():
    n,q=map(int,input().split())
    G=[[] for i in range(n)] #隣接配列
    P=[0]*n #親のポイント
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        G[a].append(b)
        G[b].append(a)
    for i in range(q):
        p,x=map(int,input().split())
        p-=1
        P[p]+=x
    
    Chk=[0]*n #訪問済みチェック
    q=deque([0])
    while q: #qが空になるまで(BFS:幅優先探索)
        now=q.popleft() #取り出す
        Chk[now]=1 #訪問済みにする
        for i in G[now]: #子に対し
            if Chk[i]==0: #未訪問のとき
                P[i]+=P[now] #ポイント加算
                q.append(i) #親としてqに入れる

    print(*P)

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


import math
H, N = list(map(int, input().split()))

AB = [list(map(int, input().split())) for _ in range(N)]

dp = [float('inf')] *(H+1)
dp[H] = 0
for a,b in AB:
    for i in range(H,-1,-1):
        if i <= H - a:
            dp[i] = min(dp[i], dp[i+a] + b)
        dp[0] = min(dp[0], min(dp[:a+1]) + b) # if hp is not just 0

print(dp[0])

### FIXED CODE ###

import math
H, N = list(map(int, input().split()))
 
AB = [list(map(int, input().split())) for _ in range(N)]
 
dp = [float('inf')] *(H+1)
dp[H] = 0
for a,b in AB:
    for i in range(H,-1,-1):
        if i <= H - a:
            dp[i] = min(dp[i], dp[i+a] + b)
    dp[0] = min(dp[0], min(dp[:a+1]) + b) # if hp is not just 0
print(dp[0])
### BUGGY CODE ###

n = int(input())
a = []
for _ in range(n):
  a.append(int(input()))
  
for i in range(n):
  tmp = a.pop(i)
  print(max(a))
  a.insert(i, tmp)


### FIXED CODE ###

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

b = sorted(a)
maxnum = b[-1]
nextmaxnum = b[-2]

if maxnum == nextmaxnum:
  for i in range(n):
    print(maxnum)
else:
  for i in range(n):
    if a[i] == maxnum:
      print(nextmaxnum)
    else:
      print(maxnum)
### BUGGY CODE ###

from sys import stdin


def get_result(data):
    N = int(data[0][0])
    S = data[1][0]
    ans = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            if S[i] != S[j]:
                for k in range(j+1, N):
                    if S[j] != S[k] and S[k] != S[i]:
                        if (j-i) != (k-j):
                            ans += 1
    return ans


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(str, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)


### FIXED CODE ###

from sys import stdin


def get_result(data):
    # N = int(data[0][0])
    S = data[1][0]
    r_index = [i for i in range(len(S)) if S[i] == 'R']
    g_index = [i for i in range(len(S)) if S[i] == 'G']
    b_index = set([i for i in range(len(S)) if S[i] == 'B'])
    all_case = len(r_index) * len(g_index) * len(b_index)
    invalid_case = 0
    for i in r_index:
        for j in g_index:
            s_i, s_j = sorted([i, j])
            tmp_max_b = s_j + (s_j-s_i)
            if tmp_max_b in b_index:
                invalid_case += 1
            tmp_min_b = s_i - (s_j-s_i)
            if tmp_min_b in b_index:
                invalid_case += 1
            tmp_mid_b = (s_i + s_j) / 2
            if tmp_mid_b in b_index:
                invalid_case += 1
    return all_case - invalid_case


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(str, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)
### BUGGY CODE ###

import itertools

n=int(input())
s=list(map(lambda _s: _s[0], filter(lambda _s: _s[0] == "M" or _s[0] == "A" or _s[0] == "R" or _s[0] == "C" or _s[0] == "H", list(input() for _ in range(n)))))

if len(s) == 0:
    print(0)
    quit()

print(len(list(filter(lambda x: len(set(x))==3, itertools.combinations(s, 3)))))


### FIXED CODE ###

import itertools
n = int(input())
s = [input()[0] for _ in range(n)]
c = list(itertools.combinations(set(filter(lambda x: x in "MARCH", s)), 3))

ans = 0
for _c in c:
    ans += s.count(_c[0])*s.count(_c[1])*s.count(_c[2])
print(ans)
### BUGGY CODE ###

from sys import stdin
lis =[]
#k = int(stdin.readline().rstrip())
lis= stdin.readline().rstrip().split()
k = int(lis[0])
s = int(lis[1])
count = 0
x = 0

for x in range(s+1):
    y = 0
    for y in range(s+1):
        z = 0
        for z in range(s+1):
            if x <= k and y <= k and z <= k and s == x + y + z:
                count +=1
            #print(x,y,z)

print(count)

### FIXED CODE ###

from sys import stdin
lis =[]
#k = int(stdin.readline().rstrip())
lis= stdin.readline().rstrip().split()
k = int(lis[0])
s = int(lis[1])
count = 0
x = 0
y = 0
z = 0
for x in range(k+1):
    y = 0
    for y in range(k+1):
        z = 0
        z = s - x - y
        if z <= k and z >= 0:
                count +=1



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

import itertools
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
Q=int(input())
B=[0]*Q;C=[0]*Q
for i in range(Q):
  B[i],C[i]=map(int,input().split())
#print(A)

S=[[0 for i in range(N)] for j in range(Q+1)]


for i in range(Q):
  for j in range(N):
    S[i][j]=A[j]
    if B[i]==A[j]:
      A[j]=C[i]
S[Q]=A
for i in range(1,Q+1):
  print(sum(S[i]))

### FIXED CODE ###

import collections
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
Q=int(input())
B=[0]*Q;C=[0]*Q
for i in range(Q):
  B[i],C[i]=map(int,input().split())

D = collections.Counter(A)
s=sum(A)
for i in range(Q):
  s=s-B[i]*D[B[i]]
  D[C[i]]+=D[B[i]]
  s=s+C[i]*D[B[i]]
  D[B[i]]=0
#  A = [C[i] if B[i]==A[j] else A[j] for j in range(N)]
#  print(A)
  print(s)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
n = int(input())
sl = list(input())[:-1]

q = int(input())
kl = list(map(int,input().split()))

for k in kl:
    # i文字目までのdとmとdmの数
    d = 0
    m = 0
    dm = 0
    ans = 0
    for i in range(n):
        if i - k >= 0:
            if sl[i-k] == "D":
                d -= 1
                dm -= m
            if sl[i-k] == "M":
                m -= 1
        if sl[i] == "D":
            d += 1
        if sl[i] == "M":
            m += 1
            dm += d
        if sl[i] == "C":
            ans += dm

    print(ans)









### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = input()
    Q = int(input())
    x = tuple(map(int,input().split()))
    for k in x:
        d,m,dm,dmc = 0,0,0,0
        for i in range(N):
            if S[i] == "D":
                d += 1
            elif S[i] == "M":
                m += 1
                dm += d
            elif S[i] == "C":
                dmc += dm
            if i >= k-1:
                if S[i-k+1] == "D":
                    dm -= m
                    d -= 1
                elif S[i-k+1] == "M":
                    m -= 1
        print(dmc)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

S = input()
S = S[::-1]
N = len(S)

mod = 10**9 + 7

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

for i, s in enumerate(S):
  if s == '?':
    R = [j*10**i % 13 for j in range(10)]
    for j in range(13):
      for r in R:
        dp[i+1][(j+r)%13] = (dp[i+1][(j+r)%13] + dp[i][j]) % mod
      
  else:
    s = int(s)
    r = s*10**i % 13
    dp[i+1] = dp[i][-r:] + dp[i][:-r]

print(dp[-1][5])

### FIXED CODE ###

S = input()
S = S[::-1]
N = len(S)

mod = 10**9 + 7

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

digit = 1
for i, s in enumerate(S):
  if s == '?':
    R = [j*digit % 13 for j in range(10)]
    for j in range(13):
      for r in R:
        dp[i+1][(j+r)%13] = (dp[i+1][(j+r)%13] + dp[i][j]) % mod
      
  else:
    s = int(s)
    r = s*digit % 13
    dp[i+1] = dp[i][-r:] + dp[i][:-r]
  
  digit *= 10
  digit %= 13

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

ans = 0
mod = 1e9+7

N = int(input())
A = [int(num)%mod for num in input().split()]

for i in range(N-1):

    for j in range(i+1, N):
        
        ans += A[i]*A[j]

ans = int(ans%mod)
print(ans)

### FIXED CODE ###

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