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

S=raw_input()
l=len(S)

mod=10**9+7

dp=[ 0  for j in range(4) ] 

all=1  #Joutai-su

for i in range(l):
	t1=dp[1]
	t2=dp[2]
	t3=dp[3]

	if S[i]=="A":
		dp[1]+=all
	elif S[i]=="B":
		dp[2]=t2+t1
	elif S[i]=="C":
		dp[3]=t3+t2
	elif S[i]=="?":
		dp[1]=t1*3+all
		dp[2]=t2*3+t1
		dp[3]=t3*3+t2
		all*=3

	dp[1]%=mod
	dp[2]%=mod
	dp[3]%=mod
	all%mod


print dp[-1]%mod


### FIXED CODE ###

S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M
### BUGGY CODE ###

from collections import defaultdict


def num_combinations(_n):
    return _n * (_n - 1) // 2


if __name__ == '__main__':
    n = int(input())
    xs = [int(s) for s in input().split()]
    freq = defaultdict(int)

    for n in xs:
        freq[n] += 1

    res = 0

    for k in range(len(xs)):
        res = 0
        for num in freq.keys():
            res += num_combinations(freq[num] - (1 if xs[k] == num else 0))
        print(res)


### FIXED CODE ###

from collections import defaultdict


def num_combinations(_n):
    return _n * (_n - 1) // 2


if __name__ == '__main__':
    n = int(input())
    xs = [int(s) for s in input().split()]
    freq = defaultdict(int)

    for n in xs:
        freq[n] += 1

    total = sum([num_combinations(n) for n in freq.values()])
    for x in xs:
        print(total - (freq[x] - 1))
### BUGGY CODE ###

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

fact_counts = [0] * (10**6+1)
def fact(n):
    if n%2 == 0:
        fact_counts[2] += 1
    while n%2 == 0:
        n //=2

    for f in range(3, int(n**0.5)+ 1, 2):
        if n%f == 0:
            fact_counts[f] += 1
        while n%f == 0:
            n //= f
    if n != 1:
        fact_counts[n] += 1

for a in A:
    fact(a)

pairwise = True
for c in fact_counts:
    if c > 1:
        pairwise = False

if pairwise:
    print('pairwise coprime')
else:
    if max(fact_counts) == n:
        print('not coprime')
    else:
        # すべてに共通する素因数が見つからなかったら
        print('setwise coprime')


### FIXED CODE ###

N = int(input())
A = tuple(map(int, input().split()))
maxa = max(A)
min_facts = [0] * (maxa+1)
def p(n):
    """ """
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if not is_prime[i]:
            continue
        min_facts[i] = i
        
        for j in range(i*2, n+1, i):
            is_prime[j] = False
            if min_facts[j] == 0:
                min_facts[j] = i
p(maxa)
fact_counts = dict()
for a in A:
    while min_facts[a] > 0:
        f = min_facts[a]
        fact_counts.setdefault(f, 0)
        fact_counts[f] += 1
        while a%f == 0:
            a //= f

pairwise = True
for c in fact_counts.values():
    if c > 1:
        pairwise = False
        break

if pairwise:
    print('pairwise coprime')
else:
    if max(fact_counts.values()) == N:
        print('not coprime')
    else:
        print('setwise coprime')
### BUGGY CODE ###

n = int(input())

a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ans_list = [0] * n
for r in range(n):
    temp = [i for i in a if b[r] > i]
    ans_list[r] = len(temp) 

ans_list2= [0] * n
for r in range(n):
    temp = [ans_list[i] for i in range(n) if c[r] > b[i]]
    ans_list2[r] += sum(temp)

print(sum(ans_list2))

### FIXED CODE ###

from bisect import bisect_left, bisect_right

n = int(input())
a = sorted(list(map(int, input().split())))
b = list(map(int, input().split()))
c = sorted(list(map(int, input().split())))

ans = 0
for i in b:
    ans += bisect_left(a, i) * (n - bisect_right(c, i))

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

N,K,Q = input().split()
N=int(N)
K=int(K)
Q=int(Q)

seikai_list = []
for i in range(Q):
  seikai_list.append(int(input()))
  
count_list = []
for n in range(N):
  count_list.append(seikai_list.count(n+1))

count_list2 = map(lambda x: x + K - Q, count_list)

for count in count_list2:
  if count > 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N,K,Q = input().split()
N=int(N)
K=int(K)
Q=int(Q)

seikai_list = [K - Q] * N
for i in range(Q):
  num = int(input()) -1
  seikai_list[num] = seikai_list[num] +1

for n in seikai_list:
  if n > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

N=int(input())
LR=[None]*N
for i in range(N):
    LR[i]=list(map(int,input().split()))

if len(LR)%2==1:
    LR=LR+[[0,0]]

RAN=(len(LR)+1)//2

LR_L=sorted(LR,key=lambda x: x[0],reverse=True)
LR_R=sorted(LR,key=lambda x: x[1])


ANS=0
for k in range(RAN):
    SUB=0
    for i in range(k+1):
        SUB+=LR_L[i][0]-LR_R[i][1]
        ANS=max(SUB,ANS)

print(ANS*2)


### FIXED CODE ###

N=int(input())
LR=[None]*N
for i in range(N):
    LR[i]=list(map(int,input().split()))

RAN=(len(LR)+1)//2

LR_L=sorted(LR,key=lambda x: x[0],reverse=True)
LR_R=sorted(LR,key=lambda x: x[1])

ANS_l=[0]*(RAN*2+2)
ANS_r=[0]*(RAN*2+2)

for i in range(RAN):
    ANS_l[2*i+1]=ANS_l[2*i]+LR_L[i][0]
    ANS_l[2*i+2]=ANS_l[2*i+1]-LR_R[i][1]

    ANS_r[2*i+1]=ANS_r[2*i]-LR_R[i][1]
    ANS_r[2*i+2]=ANS_r[2*i+1]+LR_L[i][0]


print(max(max(ANS_l)*2,max(ANS_r)*2))
### BUGGY CODE ###

a, b, k = map(int, input().split())
list_ANS = [i for i in range(a, b+1)]

for _ in range(k):
    if len(list_ANS) != 0:
        a = list_ANS.pop(0)
        print(a)
    else:
        break
list_A = []
for _ in range(k):
    if len(list_ANS) != 0:
        b = list_ANS.pop(-1)
        list_A.append(b)
    else:
        break

list_A.reverse()
for i in list_A:
    print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
if b-a > pow(10, 5):
    list_ANS = [i for i in range(a, a+pow(10, 5))] + [i for i in range(b - pow(10, 5), b+1)]
else:
    list_ANS = [i for i in range(a, b+1)]

for _ in range(k):
    if len(list_ANS) != 0:
        a = list_ANS.pop(0)
        print(a)
    else:
        break
list_A = []
for _ in range(k):
    if len(list_ANS) != 0:
        b = list_ANS.pop(-1)
        list_A.append(b)

    else:
        break
if len(list_A) != 0:
    list_A.reverse()
    for i in list_A:
        print(i)
### BUGGY CODE ###

import bisect
n = int(input())
d_li = list(map(int,input().split()))
d_li.sort()
m = int(input())
t_li = list(map(int,input().split()))
t_li.sort()
for t in t_li:
    ind = bisect.bisect_left(d_li, t)
    if ind > len(d_li) -1:
        print('NO')
        exit()
    if d_li[ind] == t:
        d_li = d_li[ind+1:]
        #print(d_li)
    else:
        print('NO')
        exit()
print('YES')


### FIXED CODE ###

import bisect
n = int(input())
d_li = list(map(int,input().split()))
m = int(input())
t_li = list(map(int,input().split()))

import collections
d_cnt = collections.Counter(d_li)
t_cnt = collections.Counter(t_li)
#print(d_cnt,t_cnt)

for t in t_cnt.items():
    #print(d_cnt,d_cnt[t[0]],t[1])
    if d_cnt[t[0]] < t[1]:
        print('NO')
        exit()
print('YES')
### BUGGY CODE ###

input_data = list(map(int,input().split()))
nums = [input_data[0],input_data[1]]
x = input_data[2]
cnt = 0
for i in range(nums[0],nums[1]+1):
    if i % x == 0:
        cnt += 1

print(cnt)

### FIXED CODE ###

a,b,x = map(int,input().split())

print(b//x-(a-1)//x)
### BUGGY CODE ###

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

### FIXED CODE ###

n,q=map(int,input().split())
s = input()
a = [0,0]
for i in range(1,n):
    a.append(a[i]+(s[i-1]=="A" and s[i]=='C'))
for i in range(q):
    l,r=map(int,input().split())
    print(a[r]-a[l-1]-(s[l-2]=='A' and s[l-1]=='C'))
### BUGGY CODE ###

n, p = map(int, input().split())
gcd = 1
f = 2

while True:
  fcnt = 0
  while p%f == 0:
    p /= f
    fcnt += 1
    if fcnt == n:
      gcd *= f
      fcnt = 0
  if f == 2:
    f = 3
  else:
    f += 2
  if f > p or n > p:
    break

print(gcd)


### FIXED CODE ###

import math
n, p = map(int, input().split())
gcd = 1
f = 2
upper = math.floor(math.pow(p, 1/n))

if n == 1:
  gcd = p
else:
  while True:
    if f > upper:
      break
    fn = f**n
    while p%fn == 0:
      gcd *= f
      p /= fn
    if f == 2:
      f = 3
    else:
      f += 2

print(gcd)
### BUGGY CODE ###

s = input()
s = s.replace("RL", "*")
i = 0
rls = []
n = 0
m = 0
for c in s:
  if c == "R":
    n += 1
  if c == "*":
    r = (n + 1) // 2
    l = n + 1 - r
    rls.append([l, r])
    n = 0
m = 0
i = 1
for c in reversed(s):
  if c == "L":
    m += 1
  if c == "*":
    l = (m + 1) // 2
    r = m + 1 - l
    rls[-i][0] += l
    rls[-i][1] += r
    i += 1
    m = 0
ans = []
i = 0
for c in s:
  if c == "*":
    ans = ans + rls[i]
    i += 1
  else:
    ans.append(0)
print(" ".join([str(c) for c in ans]))

### FIXED CODE ###

s = input()
s = s.replace("RL", "*")
i = 0
rls = []
n = 0
m = 0
for c in s:
  if c == "R":
    n += 1
  if c == "*":
    r = (n + 1) // 2
    l = n + 1 - r
    rls.append([l, r])
    n = 0
m = 0
i = 1
for c in reversed(s):
  if c == "L":
    m += 1
  if c == "*":
    l = (m + 1) // 2
    r = m + 1 - l
    rls[-i][0] += l
    rls[-i][1] += r
    i += 1
    m = 0
ans = []
i = 0
for c in s:
  if c == "*":
    ans.extend(rls[i])
    i += 1
  else:
    ans.append(0)
print(" ".join([str(c) for c in ans]))
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
count=0
N=int(input())
for i in range(1,N+1):
	for j in range(1,N+1):
		for k in range(1,N+1):
			count+=(gcd_list([i,j,k]))
print(count)


### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
count=0
N=int(input())
for i in range(1,N+1):
	for j in range(i,N+1):
		for k in range(j,N+1):
			if i==j and j==k and k==i:
				count+=(gcd_list([i,j,k]))
			elif i==j or j==k or i==k:
				count+=(gcd_list([i,j,k]))*3
			else:
				count+=(gcd_list([i,j,k]))*6

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

s=str(input())
temps=list(s)
temp=0
for i in range(0,len(temps)):
  if temps[i]=="B":
    temp=temp+s.count("W",i+1,len(s))
print(temp)

### FIXED CODE ###

s=str(input())
s=list(s)
count=0
temp=0
for i in range(len(s)):
  if s[i]=="W":
    temp=temp+i-count
    count=count+1
print(temp)
### BUGGY CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-

R,G,B,N =[int(x) for x in input().split()]
a = 0
for i in range(N//R+1):
    for j in range(((N-(i*R))//G)+1):
        if N -i*R-j*G >=0 and (N -i*R-j*G)%B == 0:
            a += 1
                       
           

print(a)

### FIXED CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-

R,G,B,N =[int(x) for x in input().split()]
a = 0
for i in range(N//R+1):
    for j in range(((N-(i*R))//G)+1):
        if (N -i*R-j*G)%B == 0:
            a += 1
                       
           

print(a)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
count = 0
for i in range(n):
    count = a[i]
    if count == 0:
        ans += 1
    for j in range(1,n-i):
        count += a[i+j]
        if count == 0:
            ans += 1
print(ans)

### FIXED CODE ###


n = int(input())
a = list(map(int,input().split()))
b = {0:0}
c = 0
for i in range(n):
    c = c+a[i]
    if c in b:
        b[c] += 1
    else:
        b[c] = 0
d = list(b.values())
ans = 0
for i in d:
    ans+= ((i+1)*i)//2
print(ans)
### BUGGY CODE ###


import  numpy as np

arr = np.array([])
N = int(input())
for _ in range(N):
  arr = np.append(arr,input())
  
print(len(np.unique(arr)))

### FIXED CODE ###


N = int(input())
ss = []
for i in range(N):
  ss.append(input())
  
print(len(set(ss)))
### BUGGY CODE ###

N = int(input())
A = list(map(lambda a : int(a), input().split(" ")))
ans = 1
for i in range(len(A)):
  ans *= A[i]
 
print(ans) if ans <= 10 ** 18 else print("-1")

### FIXED CODE ###

N = int(input())
A = list(map(lambda a : int(a), input().split(" ")))
ans = 1
if A.count(0) > 0:
  ans = 0

for i in range(len(A)):
  ans *= A[i]
  if ans > 10 ** 18:
    ans = -1
    print("-1")
    break
 
if ans != -1:
  print(ans)
### BUGGY CODE ###

n,s = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353
dp = [[0 for i in range(s+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for x in range(s+1):
        dp[i+1][x] = 2*dp[i][x]
        if x-a[i] >= 0:
            dp[i+1][x] += dp[i][x-a[i]]
        dp[i+1][x] %= mod

print(dp[n][s])

### FIXED CODE ###

n,s = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 998244353
dp = [[0 for i in range(s+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for x in range(s+1):
        dp[i+1][x] = 2*dp[i][x]
        if x-a[i] >= 0:
            dp[i+1][x] += dp[i][x-a[i]]
        dp[i+1][x] %= mod

print(dp[n][s])
### BUGGY CODE ###

def countAC(s):
    index = []
    for i in range(len(s)):
        if i == len(s)-1:
            break
        if s[i] == 'A':
            if s[i+1] == 'C':
                index.append(1)
                continue
        index.append(0)
    return index

N,Q = (int(_) for _ in input().split())
S = input()
SIndex = countAC(S)
out = 0
for i in range(Q):
    l,r = (int(_) for _ in input().split())
    s = SIndex[l-1:r-1]
    for x in s:
        out += x
    print(out)
    out = 0


### FIXED CODE ###

def countAC(s):
    counter = 0
    index = [0]
    for i in range(1,N):
        if s[i-1] == 'A':
            if s[i] == 'C':
                counter += 1
                index.append(counter)
                continue
        index.append(counter)
    return index

N,Q = (int(_) for _ in input().split())
S = input()
SIndex = countAC(S)
out = 0
for i in range(Q):
    l,r = (int(_) for _ in input().split())
    print(SIndex[r-1] - SIndex[l-1])
### BUGGY CODE ###

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

result = functools.reduce(operator.mul, A)
if result > 10**18:
    print(-1)
else:
    print(result)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
if 0 in A:
    print(0)
else:
    for i in range(N):
        ans *= A[i]
        if ans > 10**18:
            print(-1)
            exit()
    print(ans)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7
mod = 998244353


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


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, S = read_values()
    A = read_list()

    dp = [(0, 0, 0) for _ in range(S + 1)]
    dp[0] = (1, 0, 0)

    for a in A:
        for s in range(S, -1, -1):
            dp[s] = (
                dp[s][0],
                (
                    (dp[s][1] + dp[s][0]) % mod
                    + (0 if s - a < 0 else dp[s - a][0] + dp[s - a][1]) % mod
                )
                % mod,
                (
                    sum(dp[s]) % mod
                    + (0 if s - a < 0 else dp[s - a][1] + dp[s - a][0]) % mod
                )
                % mod,
            )

    print(dp[S][2])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7
mod = 998244353


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


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, S = read_values()
    A = read_list()

    dp = [(0, 0, 0) for _ in range(S + 1)]
    dp[0] = (1, 1, 1)

    for a in A:
        for s in range(S, -1, -1):
            d1 = dp[s][0]
            d2 = (dp[s][1] + (0 if s - a < 0 else dp[s - a][1]) + d1) % mod
            d3 = (dp[s][2] + (0 if s - a < 0 else dp[s - a][1]) + d2) % mod
            dp[s] = (d1, d2, d3)

    print((dp[S][2] - dp[S][1]) % mod)


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

N, X, Y = map(int, input().split())

dist = [[0 for _ in range(N)] for _ in range(N)]
ans = [0 for _ in range(N)]

for i in range(N):
    for j in range(i, N):
        tmp1 = abs(i - X + 1) + abs(j - Y + 1) + 1
        tmp2 = abs(i - Y + 1) + abs(j - X + 1) + 1
        min_dist = min(abs(i - j), tmp1, tmp2)

        ans[min_dist - 1] += 1

for i in range(N - 1):
    print(ans[i])

### FIXED CODE ###

from collections import deque

N, X, Y = map(int, input().split())

dist = [[0 for _ in range(N)] for _ in range(N)]
ans = [0 for _ in range(N)]

for i in range(N):
    for j in range(N):
        tmp1 = abs(i - X + 1) + abs(j - Y + 1) + 1
        tmp2 = abs(i - Y + 1) + abs(j - X + 1) + 1

        dist[i][j] = min(abs(i - j), tmp1, tmp2)
        dist[j][i] = min(abs(i - j), tmp1, tmp2)

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

for i in range(N - 1):
    print(ans[i])
### BUGGY CODE ###

N = int(input())
ans = 0
x = 0

while True:
    x += 1
    m = (N-x)/x
    if m % 1 == 0:
        if x < m <= N:
            ans += m
        else:
            break

print(int(ans))


### FIXED CODE ###

N = int(input())
ans = 0
x = 0

while x**2+x < N:
    x += 1
    m = (N-x)/x
    if m % 1 == 0:
        if x < m <= N:
            ans += m
        else:
            break

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

n, q = map(int, input().split())
S = input()
p = [list(map(int, input().split())) for _ in range(q)]

for l, r in p:
    sub_str = S[l-1:r]
    print(sub_str.count('AC'))

### FIXED CODE ###

n, q = map(int, input().split())
S = input()
t = [0] * (n + 1)

for i in range(n):
    t[i + 1] = t[i] + (1 if S[i:i + 2] == 'AC' else 0)

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

#event sort
import bisect
N, Q = map(int, input().split())
consts = [list(map(int, input().split())) for _ in range(N)]
events = [[0,0,0] for _ in range(2*N)]
for i,const in enumerate(consts):
    s,t,x = const
    events[2*i]=[s-x, 1, x]
    events[2*i+1]=[t-x, -1, x]
events.sort()
sets = set()
for _ in range(Q):
    d = int(input())
    eventime = [event[0] for event in events]
    index = bisect.bisect_right(eventime, d)
    for _ in range(index):
        t, pm, x = events.pop(0)
        if pm == 1:
            sets.add(x)
        if pm == -1:
            sets.remove(x)
    if len(sets)==0:
        print(-1)
    else:
        print(min(sets))

### FIXED CODE ###

from bisect import bisect_left
N, Q = map(int, input().split())
consts = []
for _ in range(N):
    s,t,x = map(int, input().split())
    consts.append((x,s,t))
consts.sort()
D=[int(input()) for _ in range(Q)]
ans=[-1]*Q
jump=[-1]*Q
for x,s,t in consts:
    left=bisect_left(D,s-x)
    right=bisect_left(D,t-x)
    while left<right:
        if jump[left]==-1:
            ans[left]=x
            jump[left]=right
            left += 1
        else:
            left=jump[left]
print(*ans, sep='\n')
### BUGGY CODE ###

# coding: utf-8

import itertools
import math


def my_generator(C):
    for v in itertools.permutations(C):
        yield v

def python_list_add(A, C):
    return [a + b for a, b in zip(A, C)]

def check(A, C):
    m = 0
    for i in range(N):
        m += C[i][0]
        A = python_list_add(A, C[i])
        # print("A", A)
        b = [i for i in range(M+1) if A[i] < X]
        # print("b", b)
        if len(b) == 0:
            return m
    else:
        print(-1)
        exit()

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

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

genlst = my_generator(C)
lenn = math.factorial(N)
m = ["" for i in range(lenn)]
for i in range(lenn):
    C = next(genlst)
    A = [0 for i in range(M+1)]
    m[i] = check(A, C)
print(min(m))


### FIXED CODE ###

# coding: utf-8
N, M, X = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(N)]
n = len(C)
m = -1
for i in range(2 ** n):
    A = [0 for i in range(M+1)]
    total = 0
    for j in range(n):
        if((i >> j) & 1):
            A = [a + b for a, b in zip(A, C[j])]
            B = [k for k in range(1, M+1) if A[k] < X]
            if len(B) == 0:
                if m == -1:
                    m = A[0]
                else:
                    m = min(m, A[0])
                break
print(m)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
later_max = [0]*(n+1)
a.insert(0, 0)
for i in range(1, n):
    later_max[i] = i + a[i] + max(a[i+1:])
    if later_max[i] > n:
        later_max[i] = n

# print(a)
# print(later_max)
count = 0
for i in range(1, n):
    j = i + a[i] + 1
    # print(f"start:{i} {j}")
    while j <= later_max[i]:
        if a[i] + a[j] == j - i:
            # print(i, j)
            count += 1
        j += 1

print(count)


### FIXED CODE ###

n = int(input())
a_array = list(map(int, input().split()))
a_array.insert(0, 0)
x_sum = {}
x_dis = {}

for i in range(1, n+1):
    a_sum = i + a_array[i]
    if a_sum in x_sum:
        x_sum[a_sum].append(i)
    else:
        x_sum[a_sum] = [i]
    if not(a_sum in x_dis):
        x_dis[a_sum] = []

    a_dis = i - a_array[i]
    if a_dis > 0:
        if a_dis in x_dis:
            x_dis[a_dis].append(i)
        else:
            x_dis[a_dis] = [i]
        if not(a_dis in x_sum):
            x_sum[a_dis] = []

# print(x_sum)
# print(x_dis)
count = 0
for k in x_sum.keys():
    count += len(x_sum[k]) * len(x_dis[k])

print(count)