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

n = int(input())
an = list(map(int, input().split()))
m = 10**9 + 7
summary = 0
for i in range(0, n-1):
    for j in range(i+1, n):
#         if i == j: continue
#         print(i, j)
        summary += (an[i] * an[j]) % m
#         print(summary)
print(summary % m)

### FIXED CODE ###

m = 10**9 + 7
n = int(input())
an = list(map(int, input().split()))
wa = []
total = 0
for i in reversed(range(1, len(an))):
    total = total + an[i]
    wa.append(total)
wa = sorted(wa, reverse=True)
ans = 0
for i in range(0, n-1):
#     print(an[i] * wa[i])
    ans = ans + an[i] * (wa[i]%m)
    ans = ans % m
print(ans)
### BUGGY CODE ###

from scipy.sparse import*
from itertools import permutations as pm

n,m,h = map(int,input().split())
r = [int(i) for i in input().split()]

A = lil_matrix((n+1,n+1))
for i in range(m):
  u,v,l = map(int,input().split())
  A[u,v] = l

A=csgraph.dijkstra(A.tocsr(),0)

s=min(sum([A[i][j] for i,j in zip(a[:-1],a[1:])]) for a in pm(r))
print(int(s))

### FIXED CODE ###

from scipy.sparse import*
from itertools import permutations as pm

n,m,h = map(int,input().split())
r = [int(i) for i in input().split()]

u,v,l = zip(*[map(int,input().split()) for i in range(m)])

A=csgraph.dijkstra(csr_matrix((l,(u,v)),(n+1,n+1)),0)

s=min(sum(A[i][j] for i,j in zip(a[:-1],a[1:])) for a in pm(r))
print(int(s))
### BUGGY CODE ###

N = int(input())
S = input()
A = [[],[],[]]
ans = 0
for i in range(N):
    if S[i] == 'R':
        A[0].append(i)
    elif S[i] == 'G':
        A[1].append(i)
    else:
        A[2].append(i)

for i in A[0]:
    for j in A[1]:
        for k in A[2]:
            if  (i < j and j < k) or (k < j and j < i):
                if abs(i-j) != abs(j-k):
                    ans += 1
            elif (i < k and k < j) or (j < k and k < i):
                if abs(i-k) != abs(k-j):
                    ans += 1
            elif (j < i and i < k) or (k < i and i < j):
                if abs(j-i) != abs(k-i):
                    ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
S = input()
A = [[],[],[]]

for i in range(N):
    if S[i] == 'R':
        A[0].append(i)
    elif S[i] == 'G':
        A[1].append(i)
    else:
        A[2].append(i)
ans = len(A[0])*len(A[1])*len(A[2])
p = 0
for i in range(N):
  for j in range(N):
    if i+j+j <= N-1:
      if S[i] != S[i+j] and S[i] != S[i+j+j] and S[i+j] != S[i+j+j]:
        p += 1

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

import sys
input = sys.stdin.readline

s = list(input())
s.pop(-1)
q = int(input())

r = 0
for i in range(q):
  tfc = input().split()
  if tfc[0] == '1':
    r += 1
    #s.reverse()
    #s = s[::-1]
  else:
    if tfc[1] == '1':
      if r % 2 == 0:
        s.insert(0, tfc[2])
      else:
        s.append(tfc[2])
    if tfc[1] == '2':
      if r % 2 == 1:
        s.insert(0, tfc[2])
      else:
        s.append(tfc[2])          
if r % 2 == 0:
  for i in s:
      print(i, end='')
else:
  for i in (reversed(s)):
    print(i, end='')



### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())
 
r = 0
for i in range(q):
  tfc = input().split()
  if tfc[0] == '1':
    r += 1
  else:
    if tfc[1] == '1':
      if r % 2 == 0:
        s.appendleft(tfc[2])
        #s.insert(0, tfc[2])
      else:
        s.append(tfc[2])
    if tfc[1] == '2':
     if r % 2 == 1:
        s.appendleft(tfc[2])
     else:
        s.append(tfc[2])          
if r % 2 == 0:
  for i in s:
      print(i, end='')
else:
  for i in (reversed(s)):
    print(i, end='')
### BUGGY CODE ###

import fractions
from functools import reduce


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

ans = []
for i in range(N):
    if i != N:
        a = A[:i] + A[i+1:]
    else:
        a = A[:i]
    ans.append(reduce(fractions.gcd, a))
print(max(ans))


### FIXED CODE ###

import fractions


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

gcd_l = [0]
gcd_r = [0]
for i in range(N):
    gcd_l.append(fractions.gcd(gcd_l[i], A[i]))
    gcd_r.append(fractions.gcd(gcd_r[i], A[-(i+1)]))
gcd_r = gcd_r[::-1]

ans = []
for i in range(N):
    ans.append(fractions.gcd(gcd_l[i], gcd_r[i+1]))

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

from functools import reduce
from operator import add

n, k = map(int, input().split())
s_law = input()

current_status = "1"
s = [0]
for h in s_law:
    if h == current_status:
        s[-1] += 1
    else:
        s.append(1)
        current_status = h

join_num = k * 2 + 1

max_rev = 0
for i, state in enumerate(s):
    if i % 2 == 1:
        continue
    max_rev = max(reduce(add, s[i:i + join_num]), max_rev)

print(max_rev)


### FIXED CODE ###

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

h = (0, S[0])
t = (0, S[0])
k = 1 if S[0] == '0' else 0
max_handstands = 1
current_handstands = 1
while True:
    if h[0] == N-1 and t[0] == N-1:
        break
    # kを維持したままtを進める
    elif t[0] < N-1 and not (t[1] == '1' and S[t[0]+1] == '0'):
        t = (t[0]+1, S[t[0]+1])
        current_handstands += 1
    # kを増やしてtを進める
    elif t[0] < N-1 and k < K and S[t[0]+1] != t[1]:
        k += 1
        t = (t[0]+1, S[t[0]+1])
        current_handstands += 1
    # kを維持したままhを進める
    elif not (h[1] == '0' and S[h[0]+1] == '1') and h[0] < t[0]:
        max_handstands = max(max_handstands, current_handstands)
        h = (h[0]+1, S[h[0]+1])
        current_handstands -= 1
    # kを減らしてtを進める
    elif S[h[0]+1] != h[1] and h[0] < t[0]:
        max_handstands = max(max_handstands, current_handstands)
        k -= 1
        h = (h[0]+1, S[h[0]+1])
        current_handstands -= 1
    else:
        raise

print(max_handstands)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mou = [0]*n
mx = 10**10
for i in range(n):
    if a[i] < mx:
        mx = a[i]
        mi =  i
a = a[i:]+a[:i]
for v in range(0,2*(a[0]+1),2):
    mou[0] = v
    for i in range(1,n):
        mou[i] = (a[i-1]-mou[i-1]//2)*2
        if mou[i]<0:
            break
    else:
        if (mou[-1]+mou[0])//2 == a[-1]:
            ans = mou[n-i:]+mou[:n-i]
            break
print(" ".join(map(str,ans)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mou = [0]*n
for i in range(1,n):
  mou[i*2%n] =  mou[(i-1)*2%n] + (a[i*2%n-1]-a[(i-1)*2%n])*2
mous = 0
for i in range(n):
  mous += a[i]-mou[i]
p = mous//n
for i in range(n):
  mou[i] += p
print(" ".join(map(str,mou)))
### BUGGY CODE ###

s = input()
res = []
ind = 0
len_s = len(s)
string = ""
while ind < len_s:
    _s = s[ind]
    if _s == "A":
        string += "A"
        ind += 1
    elif _s == "B" and ind + 1 < len_s and s[ind + 1] == "C":
        string += "BC"
        ind += 2
    else:
        if len(string) > 0:
            res.append(string)
            string = ""
        ind += 1
if len(string) > 0:
    res.append(string)


def count(string):
    cnt = 0
    ind = len(string) - 1
    res = 0
    while ind >= 0:
        s = string[ind]
        if s == "C":
            ind -= 2
            cnt += 1
        else:
            ind -= 1
            res += cnt
    return res

ans = 0
for r in res:
    ans += count(r)
print(ans)

### FIXED CODE ###

s = input()
ind = 0
len_s = len(s)
string = ""
cnt = 0
ans = 0
while ind < len_s:
    _s = s[ind]
    if _s == "A":
        cnt += 1
        ind += 1
    elif _s == "B" and ind + 1 < len_s and s[ind + 1] == "C":
        ind += 2
        ans += cnt
    else:
        cnt = 0
        ind += 1

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

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

s = 0
for i in range(len(A)):
    for j in range(i + 1, len(A)):
        s += A[i] * A[j]

print(s % (10 ** 9 + 7))

### FIXED CODE ###

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

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

print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

n,m = map(int, input().split())
tmp = 0
flg = 0
a = []
for i in range(m):
  x,y = map(int, input().split())
  if x == 1:
    tmp = y
  elif y == n:
    tmp = x
  if tmp != 0 and a.count(tmp) == 0:
    a.append(tmp)
  elif tmp != 0 and a.count(tmp) >= 1:
    flg = 1
  tmp = 0
if flg == 1:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

### FIXED CODE ###

n,m=map(int,input().split())
a=[0]*(n+1)
b=[0]*(n+1)
flg=0
for i in range(m):
  p,q=map(int,input().split())
  if (p==1 and q==n) or (p==n and q==1):
    flg=1
  elif p==1:
    a[q]=1
  elif q==1:
    a[p]=1
  elif p==n:
    b[q]=1
  elif q==n:
    b[p]=1
for i in range(1,n+1):
  if a[i]==1 and b[i]==1:
    flg=1
if flg==1:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

N = input()
N = int(N)

a_list = [0 for x in range(1000000000)]

for i in range(N):
    a = input()
    a = int(a)
    a_list[a] = (a_list[a] + 1) % 2

print(a_list.count(1))

### FIXED CODE ###

n = input()
d = {}
for x in xrange(n):
    temp = input()
    try:
        d[temp] = (d[temp] + 1) % 2
    except:
        d[temp] = 1
print sum(d.values())
### BUGGY CODE ###

N, K = map(int, input().split())
sushi = [tuple(map(int, input().split())) for i in range(N)]
point = [0 for i in range(K+1)]

sushi.sort(key=lambda x: x[1], reverse=True)

eaten_sushi = [sushi[i] for i in range(K)]
eaten_variation = [s[0] for s in eaten_sushi]
variation_count = dict([(i, eaten_variation.count(i)) for i in range(1, N+1)])
variation_number = len(set(eaten_variation))
base = sum([s[1] for s in eaten_sushi])
bonus = variation_number ** 2
point[variation_number] = base + bonus


for i in range(K, N):
    if variation_count[sushi[i][0]] > 0:
        continue

    for j in range(K-1, 0, -1):
        if variation_count[eaten_sushi[j][0]] == 1:
            continue
        base = base - sushi[j][1] + sushi[i][1]
        variation_count[sushi[j][0]] += -1
        variation_count[sushi[i][0]] = 1
        eaten_sushi.pop(j)
        eaten_sushi.append(sushi[i])
        variation_number += 1
        bonus = variation_number ** 2
        point[variation_number] = base + bonus
        break

print(max(point))


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import defaultdict
from itertools import accumulate
import heapq

def solve(N: int, K: int, t: "List[int]", d: "List[int]"):
    sushi = defaultdict(list)
    for i in range(N):
        sushi[t[i]].append(d[i])

    A = [] # 各ネタでいちばんおいしい寿司のおいしさ
    B = [] # 各ネタで2番目以降においしい寿司のおいしさリスト
    
    for v in sushi.values():
        v.sort(reverse=True)
        A.append(v[0])
        B.extend(v[1:])
    A.sort(reverse=True)
    B.sort(reverse=True)

    X = [0] + [x for x in accumulate(A)] # X[i]: Aからうまい順にi個選んだ時のおいしさ合計
    Y = [0] + [y for y in accumulate(B)] # Y[j]: Bからうまい順にj個選んだ時のおいしさ合計

    res = 0
    for i in range(1, min(len(X), K + 1)):
        if K - i < len(Y):
            res = max(res, X[i] + Y[K - i] + i ** 2) 
            # B[:i]に含まれるネタが、A[i+1:]に含まれていた場合、実際のネタ数はiより多いが、
            # その場合はiを多くとったほうが、より美味しさが大きくなる。
            # そのためres[i]が答えになりえないため、無視して良い。
    print(res)
    return


# Generated by 1.1.4 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
    t = [int()] * (N)  # type: "List[int]" 
    d = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        t[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, K, t, d)

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

n, k = map(int, input().split())
List = list(map(int, input().split()))
score = []
max = 0
index = 0
res = 0

a = n - k + 1
b = k - 1

for i in range(a):
    pre = List[i]
    for j in range(b):
        pre += List[i+j]
    #print(max)

    if max < pre:
        max = pre
        index = i
        pre = 0
    else:
        pre = 0
    
#print(index)
for i in range(index, index+k):
    res += 1 + 0.5 * (List[i]-1)
    #print(List[i])

print(res)

### FIXED CODE ###

n, k = map(int, input().split())
List = list(map(int, input().split()))
score = []
score1 = []

def cal_score(num):
    return 1 + 0.5 * (num - 1)

score.append(cal_score(List[0]))

for i in range(1, n):
    score.append(score[i - 1] + cal_score(List[i]))
    
score1.append(score[k - 1])
m = 0
for i in range(k, n):
    score1.append(score[i] - score[m])
    m += 1

#print(score)    
#print(score1)
print(max(score1))
### BUGGY CODE ###

import sys
n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#print(L)
dp = [{} for i in range(n+1)]

for i in range(n):
    Lw, Lv =L[i][0], L[i][1] #①i番目の価値を重さテーブルに代入
    dp[i+1][Lw] = Lv 
    for w, v in dp[i].items():
        dp[i+1][w] = max(dp[i+1].get(w, 0), v) #② 一つ上の行の価値と比べて大きい方を代入
        if w + Lw <=limit:
            dp[i+1][w+Lw] = max(dp[i].get(w+ Lw, 0), Lv + v) #③一つ上の行の価値をループで1つづつ取り出し、i番目の価値と足し合わせる
        
print(max(dp[-1].values()))

### FIXED CODE ###

import sys
n, limit = map(int, sys.stdin.readline().split()) 
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [dict() for i in range(n)]
#print(dp)
dp[0][L[0][1]] = L[0][0]

for i in range(1, n):
    dp[i][L[i][1]] = min(L[i][0], dp[i-1].get(L[i][1], float('inf')))
    for v, w in dp[i-1].items():
        dp[i][v] = min(dp[i-1][v], dp[i].get(v, float('inf')))
        dp[i][L[i][1] + v] = min(L[i][0] + dp[i-1][v], dp[i-1].get(L[i][1] + v, float('inf'))) 
        
ans = 0
for v, w in dp[-1].items():
    if w <=limit:
        if ans < v:
            ans = v
#print(dp)
print(ans)
### BUGGY CODE ###

H, W = [int(x) for x in input().split(" ")]


class Node:
    def __init__(self, text, pos):
        self.text = text
        self.pos = pos
        self.next_nodes = []

    def add_next(self, node):
        self.next_nodes.append(node)


nodes = dict()
for i in range(H):
    for j, text in enumerate(input()):
        nodes[(i, j)] = Node(text, (i, j))


for i in range(H):
    for j in range(W):
        node = nodes[(i, j)]
        if node.text == "#":
            continue
        for pos in [(i-1, j), (i, j-1), (i+1, j), (i, j+1)]:
            if 0 <= pos[0] <= H-1 and 0 <= pos[1] <= W-1 and nodes[pos].text == ".":
                node.add_next(nodes[pos])


def all_pats():
    pat = []
    for i in range(H):
        for j in range(W):
            pat.append((i, j))
    return pat


def search(start, end):
    queue = []
    queue.append(start)
    count = dict()
    count[start.pos] = 0

    while True:
        if not queue:
            break
        node = queue[0]
        if node.pos == end:
            break
        queue = queue[1:]

        for next_node in node.next_nodes:
            if next_node.pos in count:
                continue
            count[next_node.pos] = count[node.pos] + 1
            queue.append(next_node)
    return count[end.pos]


total = []
for start in all_pats():
    for end in all_pats():
        start_node = nodes[start]
        end_node = nodes[end]
        if start_node.text == "." and end_node.text == ".":
            res = search(start_node, end_node)
            total.append(res)

print(max(total))


### FIXED CODE ###

class Node:
    def __init__(self, text, pos):
        self.text = text
        self.pos = pos
        self.next_nodes = []

    def add_next(self, node):
        self.next_nodes.append(node)


def all_pats():
    pat = []
    for i in range(H):
        for j in range(W):
            pat.append((i, j))
    return pat


def dfs(start):
    queue = []
    queue.append(start)
    count = dict()
    count[start.pos] = 0

    while True:
        if not queue:
            break
        node = queue[0]
        queue = queue[1:]

        for next_node in node.next_nodes:
            if next_node.pos in count:
                continue
            count[next_node.pos] = count[node.pos] + 1
            queue.append(next_node)
    return max(count.values())


H, W = [int(x) for x in input().split(" ")]
nodes = dict()
for i in range(H):
    for j, text in enumerate(input()):
        nodes[(i, j)] = Node(text, (i, j))


for i in range(H):
    for j in range(W):
        node = nodes[(i, j)]
        if node.text == "#":
            continue
        for pos in [(i-1, j), (i, j-1), (i+1, j), (i, j+1)]:
            if 0 <= pos[0] <= H-1 and 0 <= pos[1] <= W-1 and nodes[pos].text == ".":
                node.add_next(nodes[pos])


all_pats = all_pats()

counts = []
for start in all_pats:
    counts.append(dfs(nodes[start]))

print(max(counts))
### BUGGY CODE ###

s = input().split()
s = list(map(int,s))
A = s[0]
B = s[1]
C = s[2]
D = s[3]
k = 0
for i in range(A,B+1):
  if i%C != 0 and i%D != 0:
    k = k + 1
print(k)

### FIXED CODE ###

s = input().split()
s = list(map(int,s))
A = s[0]
B = s[1]
C = s[2]
D = s[3]
if A%C > 0:
  i = B//C - A//C
else:
  i = B//C - A//C + 1
if A%D > 0:
  j = B//D - A//D
else:
  j = B//D - A//D + 1
from fractions import gcd
p = (C*D)//(gcd(C,D))
if A%p > 0:
  k = B//p - A//p
else:
  k = B//p - A//p + 1
print(B-A+1-(i + j - k))
### BUGGY CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
c_ = [tuple(input()) for _ in range(h)]
c = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if c_[i][j] == '@':
            c[i][j] = True
# print(x1, y1)
# print(x2, y2)

dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]
MAX = 10**7


def convert(x, y, d):
    return (x * w + y) * 4 + d


# dp = [[[(MAX, MAX)] * 4 for _ in range(w)] for _ in range(h)]
dp = [(MAX, MAX)] * (h * w * 4)

# q = [((1, 0, x1, y1, i)) for i in range(4)]
q = [((1, 0, convert(x1, y1, i))) for i in range(4)]

while q:
    c1, c2, xyd = heappop(q)
    # print(x, y, d, c1, c2)
    d = xyd % 4
    y = (xyd // 4) % w
    x = (xyd // 4) // w
    if c1 > dp[xyd][0]:
        continue
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        nxyi = convert(nx, ny, i)
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if c[nx][ny]:
            continue
        if i == d and c2 < k:
            if dp[nxyi] > (c1, c2 + 1):
                dp[nxyi] = (c1, c2 + 1)
                heappush(q, (c1, c2 + 1, nxyi))
        else:
            if dp[nxyi] > (c1 + 1, 1):
                dp[nxyi] = (c1 + 1, 1)
                heappush(q, (c1 + 1, 1, nxyi))

ans = min(dp[convert(x2, y2, i)][0] for i in range(4))
if ans == MAX:
    ans = -1
print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
c_ = [tuple(input()) for _ in range(h)]
c = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if c_[i][j] == '@':
            c[i][j] = True
# print(x1, y1)
# print(x2, y2)

dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]
MAX = 10**7


def convert(x, y, d):
    return (x * w + y) * 4 + d


# dp = [[[(MAX, MAX)] * 4 for _ in range(w)] for _ in range(h)]
dp = [MAX * (k + 1) + k] * (h * w * 4)

# q = [((1, 0, x1, y1, i)) for i in range(4)]
q = [((k + 1, convert(x1, y1, i))) for i in range(4)]

while q:
    c0, xyd = heappop(q)
    c1 = c0 // (k + 1)
    c2 = c0 % (k + 1)
    # print(x, y, d, c1, c2)
    d = xyd % 4
    y = (xyd // 4) % w
    x = (xyd // 4) // w
    if c1 > dp[xyd] // (k + 1):
        continue
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        nxyi = convert(nx, ny, i)
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if c[nx][ny]:
            continue
        if i == d and c2 < k:
            if dp[nxyi] > c1 * (k + 1) + c2 + 1:
                dp[nxyi] = c1 * (k + 1) + c2 + 1
                heappush(q, (dp[nxyi], nxyi))
        else:
            if dp[nxyi] > (c1 + 1) * (k + 1) + 1:
                dp[nxyi] = (c1 + 1) * (k + 1) + 1
                heappush(q, (dp[nxyi], nxyi))

ans = min(dp[convert(x2, y2, i)] // (k + 1) for i in range(4))
if ans == MAX:
    ans = -1
print(ans)
### BUGGY CODE ###

def main():
    S = input()
    S = S[::-1]

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

    for i in range(len(S)):
        nextdp = [0] * 13
        for j in range(13):
            if S[i] != '?':
                k = int(S[i])
                nextdp[(j+k*10**i)%13] += dp[j]
                nextdp[(j+k*10**i)%13] %= MOD
            else:
                for k in range(10):
                    nextdp[(j+k*10**i)%13] += dp[j]
                    nextdp[(j+k*10**i)%13] %= MOD
        dp = nextdp


    print(dp[5])


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    S = list(input())

    dp = [0] * 13
    dp[0] = 1
    mod = 10**9 + 7
    digit = 1
    for i in range(len(S)-1,-1,-1):
        nextdp = [0] * 13
        if S[i] == '?':
            for j in range(10):
                for k in range(13):
                    nextdp[(j * digit + k) % 13] += dp[k]
                    # あらかじめ10*9 + 7で割って余りを出しておく
                    nextdp[(j * digit + k) % 13] %= mod
        else:
            j = int(S[i])
            for k in range(13):
                nextdp[(j * digit + k) % 13] += dp[k]
                # あらかじめ10*9 + 7で割って余りを出しておく
                nextdp[(j * digit + k) % 13] %= mod
        
        digit *= 10
        # A * 桁数の13で割ったあまりは (A % 13) * (桁数 % 13)のため、桁数を13で割っておく
        digit %= 13
        dp = nextdp
    
    print(dp[5])

main()
### BUGGY CODE ###

pp = int(input()) + 1
da = list(map(int,input().split()))
da.insert(0,0)
al = 0
if da[0] == 0:
  al += 0
for k in range(1,pp):
  da[k] += da[k-1]
  if da[k]== 0:
        al += 1
for i in range(1,pp):
    for j in range(1,pp-i):
      if da[i+j] - da[i] == 0:
        al += 1
print(al)

### FIXED CODE ###

from collections import defaultdict
 
n = int(input())
a = [int(i) for i in input().split()]
 
s = 0
d = defaultdict(int)
ans = 0
d[0] = 1
 
for i in a:
    s += i
    ans += d[s]
    d[s] += 1
 
print(ans)
### BUGGY CODE ###

from collections import Counter
from itertools import combinations

N = int(input())
S = input()

s = []
counter = Counter()
for c in S:
    if counter[c] > 3:
        continue
    s.append(c)

print(len(set(combinations(s, r=3))))


### FIXED CODE ###

N = int(input())
S = input()

count = 0
for i in range(1000):
    password = '{:03}'.format(i)
    s = S
    for j in range(3):
        index = s.find(password[j])
        if index == -1:
            break
        s = s[index + 1:]
    else:
        count += 1

print(count)