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

import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    S = S[::-1]
    for i in range(l):
        if S[i] == '?':
            for q in range(10):
                for j in range(13):
                    dp[i+1][(q*mul + j)%13] += dp[i][j]
                    dp[i+1][(q*mul + j)%13] %= MOD
        else:
            for j in range(13):
                k = int(S[i])
                dp[i+1][(k*mul + j)%13] += dp[i][j]
                dp[i+1][(k*mul + j)%13] %= MOD

        mul *= 10 % 13
    # print(dp[-1])
    print(dp[-1][5] % MOD)

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    for i in range(l):
        s = S[-(i + 1)]
        if s == '?':
            for q in range(10):
                for j in range(13):
                    dp[i+1][(q*mul + j)%13] += dp[i][j]
                    dp[i+1][(q*mul + j)%13] %= MOD
        else:
            for j in range(13):
                k = int(s)
                dp[i+1][(k*mul + j)%13] += dp[i][j]
                dp[i+1][(k*mul + j)%13] %= MOD

        mul = mul * 10 % 13
    # print(dp[-1])
    print(dp[-1][5] % MOD)

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

def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    max_A = max(a for a, _ in AB)
    inf = float('inf')
    dp = [inf] * (H + max_A + 1)
    dp[0] = 0
    for i in range(1, H + max_A + 1):
        for a, b in AB:
            t1 = i - a
            if t1 < 0:
                continue
            t2 = dp[t1]
            if t2 == inf:
                continue
            if t2 + b < dp[i]:
                dp[i] = t2 + b
    print(min(dp[H:]))
main()


### FIXED CODE ###

def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for j in range(N):
            a, b = AB[j]
            if dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
    print(min(dp[H:]))


main()
### BUGGY CODE ###

def Eratosthenes(n):
	N = {i:True for i in range(2,n+1)}
	primeNumbers = []
	for i in range(2,n+1):
		if N[i]:
			primeNumbers.append(i)
			j = i*2
			while j<=n:
				N.update({j:False})
				j += i
	return primeNumbers

while True:
	P = Eratosthenes(999999)
	try:
		n = int(input())
	except EOFError:
		break
	cnt = 0
	for x in P:
		if x>n:
			break
		cnt += 1
	print(cnt)

### FIXED CODE ###

def Eratosthenes(n):
	N = [1 for i in range(0,n+1)]
	i = 3
	while i*i<=n:
		if N[i]:
			j = i*i
			while j<=n:
				N[j] = 0
				j += i*2
		i += 2
	return N

N = Eratosthenes(999999)
while True:
	try:
		n = int(input())
	except EOFError:
		break
	cnt = 0
	if n>=2:
		cnt = 1
	for i in range(3, n+1, 2):
		cnt += N[i]
	print(cnt)
### BUGGY CODE ###

N,K=map(int,input().split())
a =[0]*N
b =[0]*N
for i in range(0,N):
    a[i],b[i] =map(int,input().split())
s=0
t=0
A=0
while s<K:
    A=min(a)
    t=A
    s=s+b[a.index(A)]
    a[a.index(A)]=max(a)+A
print(t)

### FIXED CODE ###

N,K=map(int,input().split())
a =[0]*N
b =[0]*N
for i in range(0,N):
    a[i],b[i] =map(int,input().split())
c=[0]*(10**6)
for i in range(0,N):
    c[a[i]]=c[a[i]]+b[i]
s=0
i=1
while s<K:
    s=s+c[i]
    x=i
    i=i+1
print(x)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [0] * M
C = [0] * M
A.sort()
for i in range(M):
	b, c = map(int, input().split())
	B[i] = b
	C[i] = c
	for j in range(N):
		if A[j] >= c:
			break
		elif j == b:
			break
		A[j] = c
	A.sort()
	
print(sum(A))

### FIXED CODE ###

import sys, heapq
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int, input().split())
A = list(map(int, input().split()))
a = [(-i, 1) for i in A]
heapq.heapify(a)

for i in range(M):
	b, c = map(int, input().split())
	heapq.heappush(a, (-c, b))
	
ans = 0

for i in range(N):
	pop = heapq.heappop(a)
	ans += pop[0]
	if pop[1] != 1:
		heapq.heappush(a, (pop[0], pop[1] - 1))

ans *= -1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
#%%
def dfs(gr,li):
    st = []
    seen = set()
    st.append([0,-1])
    while(st):
        x,fr = st.pop()
        if(x in seen):continue
        if(fr != -1):
            li[x]+=li[fr]
        for i in gr[x]:
            if(i==fr):continue
            st.insert(0,[i,x])
        seen.add(x)

#%%
def main():
    N,Q = [int(x) for x in input().split()]
    li = [0]*N
    gp = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = [int(x) for x in input().split()]
        gp[a-1].append(b-1)
        gp[b-1].append(a-1)

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

    dfs(gp,li)
    print(*li)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N,Q = [int(x) for x in input().split()]
    li = [0]*N
    gp = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = input().split()
        a = int(a)
        b = int(b)
        gp[a-1].append(b-1)
        gp[b-1].append(a-1)

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

    st = []
    seen = set()
    st.append(0)
    while(st):
        x = st.pop()
        if(x in seen):continue
        seen.add(x)
        for i in gp[x]:
            if(i in seen):continue
            li[i]+=li[x]
            st.append(i)
    print(*li)

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

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = not True
def ddprint(x):
  if DBG:
    print(x)

n,q = inm()
s = input()
a = [0] * (n+1)
cnt = 0
prevA = False
for i in range(n):
    if s[i] == 'A':
        prevA = True
    elif s[i] == 'C':
        if prevA:
            cnt += 1
        prevA = False
    else:
        prevA = False
    a[i] = cnt

ddprint(a)

for j in range(q):
    l,r = inm()
    ddprint(str(l) + ' ' + str(r))
    print(a[r-1] - a[l-1])


### FIXED CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = not True
def ddprint(x):
  if DBG:
    print(x)

n,q = inm()
s = input()
a = [0] * (n+1)
cnt = 0
prevA = False
for i in range(n):
    if s[i] == 'A':
        prevA = True
    elif s[i] == 'C':
        if prevA:
            cnt += 1
        prevA = False
    else:
        prevA = False
    a[i] = cnt

ddprint(a)

for j in range(q):
    l,r = inm()
    ddprint(str(l) + ' ' + str(r))
    print(a[r-1] - a[l-1])
### BUGGY CODE ###

import math,collections

def f(c):
  sum=0
  for i in c.values():
    sum+=g(i,2)
  return sum

def g(n,r):
  if n==0 or n==1:return 0
  else:return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

n=int(input())
k=list(map(int,input().split()))
c=collections.Counter(k)

for i in range(n):
  c[k[i]]-=1
  print(f(c))
  c[k[i]]+=1


### FIXED CODE ###

import collections
n=int(input())
k=list(map(int,input().split()))
c=collections.Counter(k)
ans=0

for i in c.values():
  ans+=i*(i-1)//2

for i in range(n):
  print(ans-c[k[i]]+1)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
t = A[0]
for i in range(1, N):
    t *=  A[i]
if t > 1e18:
    print(-1)
else:
    print(t)


### FIXED CODE ###

#import numpy as np
N = int(input())
A = list(map(int, input().split()))
#A = np.array(A)
t = A[0]
for i in range(1,N):
    t *= A[i]
    if int(t) > 1e18:
        for j in range(i,N):
            if A[j] == 0:
                t = 0
        break
if int(t) <= 1e18:
    print(int(t))
else:
    print(-1)
### BUGGY CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    C = [int(input()) for _ in range(N)] + [None]
    C = [C[i] for i in range(N) if C[i] != C[i + 1]]

    colors = defaultdict(list)
    for i, c in enumerate(C):
        colors[c].append(i)

    N = len(C)
    # dp[i] := i個までの色の塗り方の総和
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(N):
        # i個目を塗らない
        dp[i + 1] += dp[i]
        dp[i + 1] %= MOD
        for j in colors[C[i]]:
            if j <= i:
                continue

            # ぬる
            dp[j + 1] += dp[i]
            dp[j + 1] %= MOD

    print(dp[-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    C = [int(input()) for _ in range(N)] + [-1]
    C = [C[i] for i in range(N) if C[i] != C[i + 1]]

    N = len(C)
    # dp[i] := i個までの色の塗り方の総和
    dp = [0] * N
    dp[0] = 1
    used = [-1] * (max(C) + 1)
    used[C[0]] = 0

    for i in range(1, N):
        if used[C[i]] == -1:
            dp[i] = dp[i - 1]
        else:
            dp[i] = dp[i - 1] + dp[used[C[i]]]

        dp[i] %= MOD
        used[C[i]] = i

    print(dp[-1])


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

import sys
input = sys.stdin.readline
n, q = list(map(int, input().split()))
count = (n - 2) ** 2
c = [n] * n
r = [n] * n
for _ in range(q):
  m,q = list(map(int, input().split()))
  if m == 1:
    pos = r[q-1]
    c[:pos] = [min(q, v) for v in c[:pos]] 
    r[q-1] = 1
    if q not in [1,n]:
      count -= max(0, pos - 2)
  else:
    pos = c[q-1]
    r[:pos] = [min(q, v) for v in r[:pos]]
    c[q-1] = 1
    if q not in [1,n]:
      count -= max(0, pos-2)
print(count)

### FIXED CODE ###

import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline


n, q = list(map(int, input().split()))
count = (n - 2) ** 2
c = [n] * (n + 1)
r = [n] * (n + 1)
mc = n
mr = n
for _ in range(q):
    m,q = list(map(int, input().split()))
    if m == 1:
        if q <= mc:
            count -= mr -2
            for p in range(q+1, mc):
                c[p] = mr
            c[q] = 0
            mc = q
        else:
            count -= c[q] - 2
    else:
        if q <= mr:
            count -= mc -2
            for p in range(q+1, mr):
                r[p] = mc
            r[q] = 0
            mr = q
        else:
            count -= r[q] - 2
print(count)
### BUGGY CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
    
N, M, K = map(int, input().split())

ans = 0

for i in range(1, M):
    ans += (i * (M-i) * N**2) % (10**9 + 7) 
for i in range(1, N):
    ans += (i * (N-i) * M**2) % (10**9 + 7)

ans *= cmb((N*M-2)%(10**9+7) , K-2%(10**9+7))

print(int(ans % (10**9+7)))


### FIXED CODE ###

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

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

ans = 0

for i in range(1, M):
    ans += (i * (M-i) * N**2) % (10**9 + 7) 
for i in range(1, N):
    ans += (i * (N-i) * M**2) % (10**9 + 7)

ans *= comb(N*M-2 , K-2, 10**9+7)

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

mi = lambda: map(int, input().split())
e = enumerate
n,k = mi()
m = (n+k).bit_length()
a = list(mi())
g = [None]*n

d = dict()
for i,x in e(a):
  d[x] = i
for i,x in e(a):
  g[d[x]] = ((i+1)%n,int(d[x]>=i)+int(i+1==n))
  d[x] = i
db = [g]
for _ in range(m):
  old = db[-1]
  new = [None]*n
  for i in range(n):
    p,q = old[i]
    r,s = old[p]
    new[i] = (r,q+s)
  db.append(new)
cur = 0
st = m
cs = 0
while st>=0:
  p,q = db[st][cur]
  if cs+q < k:
    cs += q
    cur = p
  else:
    st -= 1
q = list()
for x in a[cur:]:
  if x in q:
    t = x-1
    while t != x:
      t = q.pop()
  else:
    q.append(x)
print(' '.join(map(str,q)))

### FIXED CODE ###

mi = lambda: map(int, input().split())
e = enumerate
n,k = mi()
m = (n+k).bit_length()
a = list(mi())
g = [None]*n

d = dict()
for i,x in e(a):
  d[x] = i
for i,x in e(a):
  g[d[x]] = ((i+1)%n,int(d[x]>=i)+int(i+1==n))
  d[x] = i
db = [g]
for _ in range(m):
  old = db[-1]
  new = [None]*n
  for i in range(n):
    p,q = old[i]
    r,s = old[p]
    new[i] = (r,q+s)
  db.append(new)
cur = 0
st = m
cs = 0
while st>=0:
  p,q = db[st][cur]
  if cs+q < k:
    cs += q
    cur = p
  else:
    st -= 1
    
q = list()
while cur < n:
  if g[cur][1] == 0:
    cur = g[cur][0]
  elif g[cur] == (0,1):
    break
  else:
    q.append(a[cur])
    cur += 1
  
print(' '.join(map(str,q)))
### BUGGY CODE ###

#0:09
"""
ABC数
遷移を考える問題
dp[どこまでみたか][その時の状態] = になりうる場合の数
"""
S = input()
n = len(S)

dp = [[0]*3 for i in range(n+1)]
cnt = 0 #はてなの数
#初期は後で構築
mod = 10**9 + 7 

for i in range(n):
    if S[i] == "A":
        dp[i+1][0] = (dp[i][0] + int(3**(cnt))) % mod
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = dp[i][2]
    elif S[i] == "B":
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = (dp[i][0] + dp[i][1]) % mod
        dp[i+1][2] = dp[i][2]
    elif S[i] == "C":
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = (dp[i][1] + dp[i][2]) % mod
    elif S[i] == "?":
        dp[i+1][0] = (dp[i][0] * 3 + int(3**(cnt))) % mod
        dp[i+1][1] = (dp[i][1] * 3 + dp[i][0]) % mod
        dp[i+1][2] = (dp[i][2] * 3 + dp[i][1]) % mod        
        cnt += 1

print(dp[n][2]%mod)

### FIXED CODE ###

"""
We Love ABC
DP使う問題
T : 文字列
i < j < k < len(T)
Ti = "A"
Tj = "B"
Tk = "C"
i j k の順で取れたら、1カウント
- TはA, B, C, ? で構成される
- ? は　ABC のいずれか
これらを満たす場合の数

i番目の文字において、ABCのどこまで進んだか
null:   0
A   :   1
B   :   2
C   :   3

?の扱いが厄介
?があると単純に選択肢が3倍になる
A? -> AA, AB, AC
B? -> BA, BB, BC
まだ選んでいない時 : 入力の選択肢が3倍に増える
dp[i+1][1]: 
    すでにAを選んでいる時 : iまでのAの選び方が3倍に増えるので、dp[i][1]*3
    何も選んでいない場合  : ?がAになれるので、dp[i][0]を加える
ほかも同じ
"""
mod = 10**9 + 7

S = input()
N = len(S)
dp = [[0]*4 for i in range(100800)]
dp[0][0] = 1
for i in range(N):
    s = S[i]
    dp[i+1][0] = dp[i][0] 
    dp[i+1][1] = dp[i][1] 
    dp[i+1][2] = dp[i][2] 
    dp[i+1][3] = dp[i][3] 
    if s == "A":
        # Aを選ぶ選択肢がそれまでのA,?分増える
        dp[i+1][1] += dp[i][0]
    if s == "B":
        # Bを選ぶ選択肢がそれまでのAの選択肢分増える
        dp[i+1][2] = dp[i][2] + dp[i][1] 
    if s == "C":
        # Cを選ぶ選択肢がBまでを選んだ分だけ増える
        dp[i+1][3] = dp[i][3] + dp[i][2]
    if s == "?":
        # ?を選んだ場合。選択肢は3倍に広がる
        dp[i+1][0] = (3*dp[i][0])%mod
        dp[i+1][1] = (dp[i][0] + 3*dp[i][1]) % mod
        dp[i+1][2] = (dp[i][1] + 3*dp[i][2]) % mod
        dp[i+1][3] = (dp[i][2] + 3*dp[i][3]) % mod
        
# Cまで行った数を求める
print(dp[N][3]%mod)
### BUGGY CODE ###

a = [int(input()) for i in range(int(input()))]
for i in range(len(a)):
    print(max(a[:i]+a[i+1:]))


### FIXED CODE ###

a = [int(input()) for i in range(int(input()))]
sortedA = sorted(a, reverse=True)
for i in range(len(a)):
    if a[i] == sortedA[0]:
        print(sortedA[1])
    else:
        print(sortedA[0])
### BUGGY CODE ###

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

for _ in range(N):
    x=A[0]
    A.pop(0)
    if not any(x%b==0 for b in A):
        i+=1
    A.append(x)

print(i)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
key=max(A)+1 #最大値もrange(a,key,a)で計算させるため
B=[0]*key #0~Aの最大値までのlistを作成
for a in A:
    for b in range(a,key,a):
        B[b]+=1 #aの倍数を全てにBリストで1を足す
ans=0
for a in A:
    if B[a]==1: #自身しか倍数にならなかった物
        ans+=1
print(ans)
### BUGGY CODE ###

def cal():
    x = input()
    while True:
        pre = len(x)
        x = x.replace('ST', '', 10**5)
        if len(x) == pre:
            break
    print(len(x))

cal()


### FIXED CODE ###

x = input()
ans = []

for i in x:
    if i == 'S':
        ans.append(i)
    else:
        if len(ans) == 0 or ans[-1] == 'T':
            ans.append(i)
        else:
            ans.pop()
print(len(ans))
### BUGGY CODE ###

n = int(input())
ans = n-1
for i in range(1, n//2+1):
    for j in range(i, n//2+1):
        if n == i*j:
            ans_ = i + j -2
            ans = min(ans, ans_)
print(ans)

### FIXED CODE ###

import sys
n = int(input())
for i in range(int(n**0.5), 0, -1):
    if n%i==0:
        j=n//i
        print(i+j-2)
        sys.exit()
### BUGGY CODE ###

def solve(N, W, weight_values):
  dp = [0 for _ in range(W + 1)]
  dp[0] = 0

  for i in range(N + 1):
    i_weight, i_value = weight_values[i - 1]
    for w in range(W, -1, -1):
      if i_weight <= w:
        dp[w] = max(dp[w - i_weight] + i_value, dp[w])
      else:
        dp[w] = dp[w]

  print(dp[W])

  
def iln(): return list(map(int, input().split()))


N, W = iln()
w_v = []
for i in range(N):
  w_v.append(iln())
  
solve(N, W, w_v)


### FIXED CODE ###

def solve(N, W, weight_values):
  dp = [0 for _ in range(W + 1)]

  for i in range(N):
    i_weight, i_value = weight_values[i]
    for w in range(W, i_weight - 1, -1):
      # dp[w] = max(dp[w - i_weight] + i_value, dp[w])
      temp = dp[w - i_weight] + i_value
      if temp > dp[w]:
        dp[w] = temp

  print(dp[W])

  
def iln(): return list(map(int, input().split()))


N, W = iln()
w_v = []
for i in range(N):
  w_v.append(iln())
  
solve(N, W, w_v)
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()
    lst = list(S)

    a = ['{:03d}'.format(i) for i in range(1000)]
    count = 0
    for i in range(len(a)):
        m,n,o = 0,1,2
        s = list(a[i])
        while m < n < o < len(lst) :
            if s[0] != lst[m]:
                m += 1
                n += 1
                o += 1
            elif s[1] != lst[n]:
                n += 1
                o += 1
            elif s[2] != lst[o]:
                o += 1
            else:
                count += 1
                break

    print(count)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    lst = list(S)

    a = ['{:03d}'.format(i) for i in range(1000)]
    count = 0
    for i in range(len(a)):
        m,n,o = 0,1,2
        s = list(a[i])
        while m < n < o < len(lst) :
            if s[0] != lst[m]:
                m += 1
                n += 1
                o += 1
            elif s[1] != lst[n]:
                n += 1
                o += 1
            elif s[2] != lst[o]:
                o += 1
            else:
                count += 1
                break

    print(count)

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

import copy
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [list(map(int,inputs().split())) for p in [0]*N]
M = [int(inputs()) for p in [0]*Q]
V.sort(key = lambda x:(x[2],x[0],x[1]))

for v in V:
	v[0] -= v[2]
	v[1] -= v[2] + 1
for m in M:
	for n in range(N):
		if V[n][0] <=m and m <= V[n][1]:
			print(V[n][2])
			break
	else:
		print(-1)

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

n = int(input())

li1 = []
for _ in range(n):
    s = list(input())
    li1.append(sorted(s))


li2 = []
for i in li1:
    s = ''.join(i)
    li2.append(s)

cnt = 0
for i in set(li2):
    cnt1 = li2.count(i)
    cnt += (cnt1*(cnt1-1))//2
    
print(cnt)

### FIXED CODE ###

n = int(input())

li1 = []
for _ in range(n):
    s = list(input())
    li1.append(sorted(s))

cnt = 0
li2 = sorted(li1)
li3 = []
for i in range(1, len(li2)):
    if li2[i] == li2[i-1]:
        cnt += 1
    else:
        li3.append(cnt)
        cnt = 0
    if i == len(li2)-1:
        li3.append(cnt)

cnt1 = 0
for i in li3:
    cnt1 += (i*(i+1))//2
    
print(cnt1)
### BUGGY CODE ###

def resolve():
    n=int(input())
    a = list(map(int, input().split()))
    b=[0]*n
    c=[0]*n
    ans=0
    for i in range(n):
        b[i]=a[i]+i
    for i in range(n):
        c[i]=i-a[i]
    bc=set(b).intersection(set(c))
    bd={}
    cd={}
    for i in bc:
        bd[i]=0
        for j in b:
            if j==i:
                bd[i]+=1
    for i in bc:
        cd[i]=0
        for j in c:
            if j ==i:
                cd[i]+=1
    ansb=list(bd.values())
    ansc=list(cd.values())
    for k in range(len(bc)):
        ans+=ansb[k]*ansc[k]
    print(ans)
resolve()

### FIXED CODE ###

def resolve():
    n=int(input())
    a = list(map(int, input().split()))
    b=[0]*n
    c=[0]*n
    ans=0
    for i in range(n):
        b[i]=a[i]+i
    for i in range(n):
        c[i]=i-a[i]
    bc=set(b).intersection(set(c))
    bd={}
    cd={}
    for i in bc:
        bd[i]=0
    for j in b:
            if j in bc:
                bd[j]+=1
    for i in bc:
        cd[i]=0
    for j in c:
            if j in bc:
                cd[j]+=1
    ansb=list(bd.values())
    ansc=list(cd.values())
    for k in range(len(bc)):
        ans+=ansb[k]*ansc[k]
    print(ans)
resolve()