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

"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
from heapq import*
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
data=[[] for i in range(N)]

for i in range(N):
    for m in range(N):
        if i==m:
            continue
        data[i].append([m,A[i][m],i*300+m])



visited={0}
stack=[]
dic={}
for p,c,i in data[0]:
    if c in dic:
        dic[c].append([p,i])
    else:
        dic[c]=[[p,i]]
    stack.append(c)
heapify(stack)
value=0
usedpath=set()
while stack:
    m=heappop(stack)
    a,i=dic[m].pop()
    if not a in visited:
        visited.add(a)
        usedpath.add(i)
        value+=m
        for p,c,i in data[a]:
            if not p in visited:
                if c in dic:
                    dic[c].append([p,i])
                else:
                    dic[c]=[[p,i]]
                heappush(stack,c)

idle_max=10**18
d=[[idle_max for i in range(N)] for m in range(N)]
for i in range(N):
    d[i][i]=0
for i in usedpath:
    i,m=i//300,i%300
    d[i][m]=A[i][m]
    d[m][i]=A[m][i]

for k in range(N):
    for i in range(N):
        for j in range(N):
             d[i][j] = min(d[i][j], d[i][k] + d[k][j])
Alst=[[A[i][m],i,m] for i in range(N) for m in range(N)]
Alst=sorted(Alst,key=lambda x:x[0])
for B,i,m in Alst:
    if d[i][m]<A[i][m]:
        print(-1)
        exit()
    if d[i][m]>A[i][m]:
        d[i][m]=A[i][m]
        d[m][i]=A[m][i]
        value+=A[i][m]

        for i1 in range(N):
            for j in range(N):
                 d[i1][j] = min(d[i1][j], d[i1][i] + d[i][j])
                 d[i1][j] = min(d[i1][j], d[i1][m] + d[m][j])


print(value)


### FIXED CODE ###

"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
from heapq import*
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j]>A[i][k]+A[k][j]:
                print(-1)
                exit()
res = 0
for i in range(N-1):
    for j in range(i+1, N):
        for k in range(N):
            if k==i or k == j:
                continue
            if A[i][j]==A[i][k]+A[k][j]:
                break
        else:
            res += A[i][j]
print(res)
### BUGGY CODE ###

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

S1 = set()
for i in range(N):
    a = L[i]
    for j in range(i):
        b = L[j]
        for k in range(j):
            c = L[k]
            if a < b + c:
                S1.add(tuple(sorted((i, j, k))))
S2 = set()
for i in range(N):
    b = L[i]
    for j in range(i):
        c = L[j]
        for k in range(j):
            a = L[k]
            if b < c + a:
                S2.add(tuple(sorted((i, j, k))))
S3 = set()
for i in range(N):
    c = L[i]
    for j in range(i):
        a = L[j]
        for k in range(j):
            b = L[k]
            if c < a + b:
                S3.add(tuple(sorted((i, j, k))))
print(len(S1.intersection(S2).intersection(S3)))

### FIXED CODE ###

import bisect
import random

def test(L):
    lst = []
    N = len(L)
    for a in range(N):
        for b in range(a):
            for c in range(b):
                if L[a] < L[b] + L[c]:
                    lst.append((c, b, a))
    return lst

def test_len(L):
    return len(test(L))

def test2(L):
    return len(set((l[0], l[2]) for l in test(L)))

N = int(input())
L = sorted(map(int, input().split()))
# L = [1, 1, 1000]
# L = [218, 233, 389, 645, 704, 728, 786]
# N = 10
# L = sorted([random.randint(0, 1000) for _ in range(N)])
# L = [150, 190, 192, 281, 294, 374, 501, 686, 769, 954]
# print(L)
# N = len(L)
S = 0
for a in range(2, N):
    c = bisect.bisect_left(L, (L[a] + 2) // 2)
    while c >= 0:
        if L[a] < L[c] * 2:
            c -= 1
        else:
            break
    b = c + 1
    assert L[a] < L[b] * 2
    if b == 0:
        # print("b0", b, a, (a - 1) * (a) // 2)
        S += (a - 1) * (a) // 2
        continue
    if c >= a - 1:
        continue
    assert L[a] < L[b] + L[b]
    assert L[a] >= L[c] + L[c], (a, c)
    S += (a - b) * (a - b - 1) // 2
    while c >= 0:
        while L[a] >= L[b] + L[c]:
            b += 1
        assert L[a] < L[b] + L[c]
        assert L[a] >= L[b - 1] + L[c]
        # print(c, b, a)
        S += a - b
        c -= 1
print(S)
# print(test_len(L))
### BUGGY CODE ###

n = int(input())
s = str(input().replace(' ', ''))
cnt = [0 for i in range(n)]
conb = [0 for i in range(n)]
for i in range(n):
    cnt[i] = s.count(str(i + 1))
    conb[i] = cnt[i] * (cnt[i] - 1) // 2
for k in range(n):
    ans = sum(conb) - conb[int(s[k]) - 1] + (cnt[int(s[k]) - 1] - 1) * (cnt[int(s[k]) - 1] - 2) // 2
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = [0] * (n + 1)
for i in range(n):
    cnt[a[i]] += 1
conb1, conb2 = [], []
for i in range(n + 1):
    conb1.append(cnt[i] * (cnt[i] - 1) // 2)
    if cnt[i] == 0:
        conb2.append(0)
    else:
        conb2.append((cnt[i] - 2) * (cnt[i] - 1) // 2)
sumall = sum(conb1)
for i in range(n):
    ans = sumall - conb1[a[i]] + conb2[a[i]]
    print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
count = 0
def findlet(let,ind):
    add = st[ind:].count(let)
    if add > 0:
        if 2*ind < len(st):
            if st[2*ind] == let:
                add -= 1
        return add
    return 0
for i in range(N-2):
    if i == 0:
        st = S
    else:
        st = st[1:]
    if st[0] == "R":
        for j in [x for x, y in enumerate(st) if y == 'G']:
            count += findlet("B",j)
        for j in [x for x, y in enumerate(st) if y == 'B']:
            count += findlet("G",j)
    elif st[0] == "G":
        for j in [x for x, y in enumerate(st) if y == 'B']:
            count += findlet("R",j)
        for j in [x for x, y in enumerate(st) if y == 'R']:
            count += findlet("B",j)
    else:
        for j in [x for x, y in enumerate(st) if y == 'R']:
            count += findlet("G",j)
        for j in [x for x, y in enumerate(st) if y == 'G']:
            count += findlet("R",j)
print(count)

### FIXED CODE ###

N = int(input())
S = input()
r = S.count('R')
g = S.count('G')
b = S.count('B')
count = r * g * b
for i in range(N):
    for j in range(i+1,N-1):
        if 2*j - i <= N-1:
            l = set([S[i],S[j],S[2*j-i]])
            if len(l) == 3:
                count -= 1
print(count)
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
cnt = 0
for i in range(N):
    Pi = P[i]
    for j in range(i):
        Pj = P[j]
        #print(Pj)
        if Pi > Pj:
            cnt +=1
            break
cnt = len(P)-cnt
print(cnt)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
Min = P[0]
cnt = 0
for Pi in P:
    if Pi <= Min:
        Min = Pi
        cnt +=1
print(cnt)
### BUGGY CODE ###

import bisect as bis

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

res = 0
for i, a in enumerate(L):
    for k, b in enumerate(L[i + 1:]):
        j = k + i + 1

        left = b - a
        right = a + b

        index_l = bis.bisect_right(L, left, j)
        index_r = bis.bisect_left(L, right, j)
        res += index_r - index_l - 1
print(res)



### FIXED CODE ###

import bisect as bis

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

res = 0
for i, a in enumerate(L):
    for k, b in enumerate(L[i + 1:]):
        j = k + i + 1

        left = b - a
        right = a + b

        index_l = bis.bisect_right(L, left, j)
        index_r = bis.bisect_left(L, right, j)
        if index_l == N - 1:
            break

        res += index_r - index_l - 1
print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import bisect

n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
ans=0
k=0
while i<=n-1:
    if x[i][1]>=1:
        w=x[i][1]
        ans+=w
        q=bisect.bisect_right(y,x[i][0]+2*d,i,n)
        for j in range(q-i):
            if x[i+j][1]<=0:
                continue
            else:
                x[i+j][1]-=w
    i=i+k
    k=0
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
import collections
from collections import deque
n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
# 累積ダメージを管理
qq=deque([])
ans=0
atk=0
for i in range(n):
    w=x[i][1]
    # iがダメージの有効期限を超過している場合
    while len(qq)>0 and i > qq[0][0]:
        atk-=qq[0][1]
        qq.popleft()

    if w-atk>0:
        ans+=w-atk
        q=bisect.bisect_right(y,x[i][0]+2*d)-1
        # 有効期限　ダメージ
        qq.append([q,w-atk])
        atk += w - atk
print(ans)
### BUGGY CODE ###

from collections import defaultdict
from heapq import heapify, heappop, heappush
CostMax = 10**9
inpl = lambda: list(map(int,input().split()))
H, N = inpl()
AB = [inpl() for _ in range(N)]
AB.sort(key=lambda x: (x[1], -x[0]))
A = []
B = []
for a, b in AB:
    if len(A)==0 or a > A[-1]:
        A.append(a)
        B.append(b)
L = len(A)
prevcost = defaultdict(lambda: CostMax)

q = [(0,0,0)] # position, last, cost
ans = CostMax
while q:
    pos, last, cost = heappop(q)
    if cost >= prevcost[pos]:
        continue
    else:
        prevcost[pos] = cost
        for n in range(last,L):
            new_pos = pos + A[n]
            new_cost = cost + B[n]
            if new_cost > ans:
                continue
            elif new_pos >= H:
                ans = min(ans, new_cost)
            else:
                heappush(q, (new_pos, n, new_cost))
print(ans)

### FIXED CODE ###

inpl = lambda: list(map(int,input().split()))
H, N = inpl()
A = []
B = []
for _ in range(N):
    a, b = inpl()
    A.append(a)
    B.append(b)

Max = 10**9
dp = [Max] * (H+1)
dp[0] = 0
for h in range(H):
    if dp[h] >= Max:
        continue
    for n in range(N):
        k = h + A[n]
        if k > H:
            k = H
        dp[k] = min(dp[h]+B[n], dp[k])
print(dp[H])
### BUGGY CODE ###

n, a, b = map(int, input().split())
k = 1
for i in range(n):
  k = 2*k % (10**9 + 7)
N = k - 1
import math
def combinations_count(m, r):
  return math.factorial(m) // (math.factorial(m - r) * math.factorial(r))
A = combinations_count(n, a)
B = combinations_count(n, b)
if a == b:
  print((N-A) % (10**9 + 7))
else:
  print((N-A-B) % (10**9 + 7))

### FIXED CODE ###

def ncr(n, r, p): 
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p 
    return (num * pow(den, p - 2, p)) % p
  
p = 10**9+7
n,a,b = map(int,(input().split()))

bb = ncr(n,a,p)+ncr(n,b,p)+1
print((pow(2,n,p)-(bb%p))%p)
### BUGGY CODE ###

N = int(input())

for h in range(1, 3501):
	for n in range(1, 3501):
		wb = 4*h*n - N*n - N*h
		if wb <= 0:
			continue
		w = N*h*n / wb
		if w.is_integer():
			print(h, n, int(w))
			exit()

### FIXED CODE ###

N = int(input())

for h in range(1, 3501):
	for n in range(1, 3501):
		wb = 4*h*n - N*n - N*h
		if wb <= 0:
			continue
		w = N*h*n / wb
		if w.is_integer():
			print(h, n, int(w))
			exit()
### BUGGY CODE ###

from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    que = deque()
    que.append([0, 0])
    if s[0][0] == '#':
        d[0][0] = 1
    else:
        d[0][0] = 0

    while que:
        p = que.popleft()
        if p[0] == h-1 and p[1] == w-1:
            break

        for i in range(2):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                que.append([ny, nx])
                if s[p[0]][p[1]] == '.' and  s[ny][nx] == '#':
                    d[ny][nx] = min(d[ny][nx], d[p[0]][p[1]]+1)
                else:
                    d[ny][nx] = min(d[ny][nx], d[p[0]][p[1]])

    return d[h-1][w-1]

h, w = MAP()
s = [input() for i in range(h)]
d = [[inf]*w for i in range(h)]

dy = [1, 0]
dx = [0, 1]

print(bfs())

### FIXED CODE ###

from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    que = deque()
    que.append([0, 0])
    if s[0][0] == '#':
        d[0][0] = 1
    else:
        d[0][0] = 0

    while que:
        p = que.popleft()
        if p[0] == h-1 and p[1] == w-1:
            break

        for i in range(2):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                if s[p[0]][p[1]] == '.' and  s[ny][nx] == '#':
                    if d[ny][nx] > d[p[0]][p[1]]+1:
                        d[ny][nx] = d[p[0]][p[1]]+1
                        que.append([ny, nx])
                else:
                    if d[ny][nx] > d[p[0]][p[1]]:
                        d[ny][nx] = d[p[0]][p[1]]
                        que.append([ny, nx])

    return d[h-1][w-1]

h, w = MAP()
s = [input() for i in range(h)]
d = [[inf]*w for i in range(h)]

dy = [1, 0]
dx = [0, 1]

print(bfs())
### BUGGY CODE ###

from collections import defaultdict
h, w, m = map(int, input().split())
targets = defaultdict(int)
targets_count_yoko = defaultdict(int)
targets_count_tate = defaultdict(int)
for _ in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    targets_count_yoko[x] += 1
    targets_count_tate[y] += 1
    targets[(y, x)] = -1

max_row = max(targets_count_yoko.values())
max_line = max(targets_count_tate.values())
y_idx = []
x_idx = []
max_count_x = 0
max_count_y = 0
for i in range(w):
    if targets_count_yoko[i] == max_row:
        x_idx.append(i)
        max_count_x += 1
for i in range(h):
    if targets_count_tate[i] == max_line:
        y_idx.append(i)
        max_count_y += 1


ans = max_line + max_row
kumi = max_count_x*max_count_y
for key_y, key_x in targets.keys():
    if key_y in y_idx and key_x in x_idx:
        kumi -= 1

if kumi > 0:
    print(ans)
else:
    print(ans-1)



### FIXED CODE ###

from collections import defaultdict
h, w, m = map(int, input().split())
targets = defaultdict(int)
targets_count_yoko = defaultdict(int)
targets_count_tate = defaultdict(int)
for _ in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    targets_count_yoko[x] += 1
    targets_count_tate[y] += 1
    targets[(y, x)] = -1

max_row = max(targets_count_yoko.values())
max_line = max(targets_count_tate.values())
y_idx = defaultdict(bool)
x_idx = defaultdict(bool)
max_count_x = 0
max_count_y = 0
for i in range(w):
    if targets_count_yoko[i] == max_row:
        x_idx[i] = True
        max_count_x += 1
for i in range(h):
    if targets_count_tate[i] == max_line:
        y_idx[i] = True
        max_count_y += 1


ans = max_line + max_row
kumi = max_count_x*max_count_y
for key_y, key_x in targets.keys():
    if y_idx[key_y] and x_idx[key_x]:
        kumi -= 1
    if kumi == 0:
        break

if kumi == 0:
    print(ans-1)
else:
    print(ans)
### BUGGY CODE ###

N = int(input())
As = [int(i) for i in input().split()]

T = ( sum(map(lambda t: (-1)**(t[0]%2+1) * t[1], enumerate(As[:-1])) ) + As[-1] ) / 2

for i in range(N-1):
    U = sum(map(lambda t: (-1)**(t[0]%2) * t[1], enumerate(As[i:-1])) )
    U += (-1)**(i%2) * T
    print(int(U)*2, end=" ")

print(int(T)*2)

### FIXED CODE ###

N = int(input())
As = [int(i) for i in input().split()]

x_0 = sum(As) - 2 * sum(As[1::2])
print(int(x_0), end=" ")
x = x_0

for i in range(N-2):
    x = 2*As[i] - x
    print(int(x), end=" ")

x = 2*As[N-2] - x
print(int(x))
### BUGGY CODE ###

def main():
    s = input()
    q = int(input())

    hanten = 0 # 偶数なら正常、 奇数なら反転状態

    for _ in range(q):
        tmp = input()
        if len(tmp) == 1:
            hanten += 1
        else:
            if (hanten % 2) == 0:
                if tmp[2] == '1':
                    s = tmp[4] + s
                else:
                    s = s + tmp[4]
            else:
                if tmp[2] == '1':
                    s = s + tmp[4]
                else:
                    s = tmp[4] + s

    if hanten % 2 == 0:
        print(s)
    else:
        print(s[::-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
    s = input()
    q = int(input())

    hanten = 0 # 偶数なら正常、 奇数なら反転状態

    front = "" # リストの前に追加するのは、O(n)なので避ける
    back = ""

    for _ in range(q):
        tmp = readline().split()
        if len(tmp) == 1:
            hanten ^= 1
        else:
            if hanten: # 反対ver
                if tmp[1] == '1':
                    back += tmp[2]
                else:
                    front += tmp[2]
            else: # 正常
                if tmp[1] == '1':
                    front += tmp[2]
                else:
                    back += tmp[2]

    if hanten == 0:
        print(front[::-1] + s + back)
    else:
        print((front[::-1] + s + back)[::-1])

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

n, m = map(int, input().split())
lp, ls = [0] * m, [0] * m
for i in range(m):
    lp[i], ls[i] = input().split()

lpu = list(set(lp))
lac = [0] * len(lpu)
lwa = [0] * len(lpu)

for e, i in enumerate(lpu):
    if lac[e] == 0:
        for j in range(m):
            if lp[j] == i and ls[j] == 'WA':
                lwa[e] += 1
            if lp[j] == i and ls[j] == 'AC':
                lac[e] = 1
                break
        else:
            lwa[e] = 0
    else:
        break

print(sum(lac), sum(lwa))

### FIXED CODE ###

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

lac = [0] * n
lwa = [0] * n

for i in range(m):
    p, s = input().split()
    p = int(p) - 1
    if lac[p] == 0:
        if s == 'WA':
            lwa[p] += 1
        if s == 'AC':
            lac[p] = 1

lwa = [x * y for x, y in zip(lac, lwa)]
print(sum(lac), sum(lwa))
### BUGGY CODE ###

while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  H = range(h)
  A = [0]*h
  for i in H:
    x = raw_input().replace(".", "1").replace("*", "0")
    A[i] = map(int, list(x))
  B = A[:]
  C = [0]*h
  for j in H[1:]:
    M = ["1","11","111"]
    for i in H[j:]:
      x = [e1 & e2 for e1, e2 in zip(B[i-j], A[i])]
      B[i-j] = x[:]
      x=sorted("".join(map(str, x)).split("0"))
#      M.append(x[-1])
    C[j] = len(sorted(M)[-1])*(j+1)
  print max(C)

### FIXED CODE ###

while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  M = [0]*(h+1)
  a=[0]*w
  for i in range(h):
    x = raw_input()
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]=="*": c=0
      else: c=a[j]+1
      b[j]=c
      dw=c-sp
      if dw>0: C[sp+1:c+1]=[j]*dw
      elif dw<0:
        for k in range(c+1,sp+1): M[k]=max(M[k],j-C[k])
        C[c+1:sp+1]=[-1]*(-dw)
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0: M[k]=max(M[k],w-C[k])
    a=b
  s=max([a*b for a,b in zip(M, range(h+1))])
  print s
### BUGGY CODE ###

import itertools
def my_index_multi(l, x):
    return [k for k, _x in enumerate(l) if _x == x]

h,w,m = map(int,input().split())
l_h = [0]*(h+1)
l_w = [0]*(w+1)
l_hw = [[] for _ in range(h+1)]

for _ in range(m):
    h,w = map(int,input().split())
    l_h[h] += 1
    l_w[w] += 1
    l_hw[h].append(w)

m_h = max(l_h)
m_w = max(l_w)

ans = m_h + m_w

l_h_2 = my_index_multi(l_h,m_h)
l_w_2 = my_index_multi(l_w,m_w)


for i,j in itertools.product(l_h_2,l_w_2):
    if j not in l_hw[i]:
        break
else:
    ans -= 1

print(ans)

### FIXED CODE ###

import sys
import itertools

input = sys.stdin.readline

def my_index_multi(l, x):
    return [k for k, _x in enumerate(l) if _x == x]

h,w,m = map(int,input().split())
l_h = [0]*(h+1)
l_w = [0]*(w+1)
l_b = set()

for _ in range(m):
    h,w = map(int,input().split())
    l_h[h] += 1
    l_w[w] += 1
    l_b.add((h,w))

m_h = max(l_h)
m_w = max(l_w)

l_h_2 = []
for i, x in enumerate(l_h):
    if x == m_h:
        l_h_2.append(i)

l_w_2 = []
for i, x in enumerate(l_w):
    if x == m_w:
        l_w_2.append(i)

ans = m_h + m_w

for i,j in itertools.product(l_h_2,l_w_2):
    if (i,j) not in l_b:
        break
else:
    ans -= 1

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

S=input()
N=len(S)
mod=13
mod2=10**9+7

#i桁目までみて，あまりがjになるものの個数
dp=[[0]*mod for _ in range(N+1)]

#1桁目
if S[-1]!="?":
    a=int(S[-1])
    for j in range(mod):
        dp[1][a]=1
else:
    for j in range(mod):
        for k in range(10):
            dp[1][k]=1

for i in range(1,N):
    if S[-i-1]!="?":
        a=(pow(10,i)*int(S[-i-1]))%mod
        for j in range(mod):
            dp[i+1][(j+a)%mod]=dp[i][j]
    else:
        a=pow(10,i)%mod
        for j in range(mod):
            for k in range(10):
                dp[i+1][(j+k*a)%mod]+=dp[i][j]
                dp[i+1][(j+k*a)%mod]%=mod2

print(dp[-1][5])

### FIXED CODE ###

S=input()
N=len(S)
mod=13
mod2=10**9+7

#上からi桁目までみて，あまりがjになるものの個数
dp=[[0]*mod for _ in range(N+1)]

dp[0][0]=1

for i in range(N):
    if S[i]!="?":
        for j in range(mod):
            dp[i+1][(10*j+int(S[i]))%mod]=dp[i][j]
    else:
        for j in range(mod):
            for k in range(10):
                dp[i+1][(10*j+k)%mod]+=dp[i][j]%mod2

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

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

for i in range(N-2):
    j = i + 1
    while j <= N-1:
        if A[j] + A[i] == j - i:
            ans += 1
        else:
        	pass
        j += 1
print(ans)

### FIXED CODE ###

N = int(input())
dic = {}
ans = 0
A = list(map(int, input().split()))
for i in range(N):
    dic[i] = 0

for i in range(N):
    b = A[i]+N-i-1
    if A[i] < N-i:
        a = N-i-A[i]-1
        dic[a] += 1
    if b < N:
        ans += dic[b]
print(ans)
### BUGGY CODE ###

n = int(raw_input())
travel = [map(int, raw_input().split()) for i in range(n)]

accessible_now = [(0,0)]
limit = 1e5 + 1

stroke = 0
for target in travel:
  t, x, y = target
  while (stroke<t):
    stroke += 1
    accessible_next = [] 
    for loc in accessible_now:
      for step in [(1,0),(0,1),(-1,0),(0,-1)]:
        loc_next = (loc[0]+step[0],loc[1]+step[1])
        if ((-1 in loc_next) or (limit in loc_next)):
          continue
        if (loc_next in accessible_next):
          continue
        accessible_next.append(loc_next)
    accessible_now = accessible_next
    #print stroke, t, accessible_now
    if (stroke == t):
      if ((x,y) in accessible_now):
        continue
      else:
        print 'No'
        exit(0) 
res = 'Yes' if (stroke==t) else 'No'
print res


### FIXED CODE ###

n = int(raw_input())
travel = [map(int, raw_input().split()) for i in range(n)]

loc = (0,0)
now = 0
res = 'Yes'

for dest in travel:
  t, x, y = dest
  minpath = abs(x-loc[0]) + abs(y-loc[1])
  tmp = (t-now)-minpath
  if (tmp%2==0 and tmp>=0 ):
    loc = (x,y)
    now = t
    continue
  else:
    res = 'No'
    break
print res