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

from collections import deque, defaultdict
import sys
input=sys.stdin.readline


def solve():
    H, W, K = map(int, input().split())
    y1, x1, y2, x2 = map(int, input().split())
    l = [[1 if s=="@" else 0 for s in input()] for _ in range(H)]
    INF = 10**12

    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    ddy = [0, 0, -1, 1]
    ddx = [-1, 1, 0, 0]

    dist = defaultdict(lambda :INF)
    dist[(y1, x1)] = 0
    q = deque([(y1, x1)])

    while q:
        y, x = q.popleft()
        for i in range(4):
            dx = ddx[i]
            dy = ddy[i]
            for j in range(1, K+1):
                if not (0<=y+dy*j<H and 0<=x+dx*j<W):
                    break
                if l[y+dy*j][x+dx*j]:
                    break

                if dist[(y+dy*j, x+dx*j)] >= dist[(y, x)] + 1:
                    dist[(y+dy*j, x+dx*j)] = dist[(y, x)] + 1
                    q.append((y+dy*j, x+dx*j))
                else:
                    break


    ans = dist[(y2, x2)]
    print(ans if ans!=INF else -1)


if __name__ == "__main__":
    solve()


### FIXED CODE ###

from collections import deque, defaultdict
import sys
input=sys.stdin.readline


def solve():
    H, W, K = map(int, input().split())
    y1, x1, y2, x2 = map(int, input().split())
    l = [[1 if s=="@" else 0 for s in input()] for _ in range(H)]
    INF = 10**12

    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    ddy = [0, 0, -1, 1]
    ddx = [-1, 1, 0, 0]

    dist = defaultdict(lambda :INF)
    dist[(y1, x1)] = 0
    q = deque([(y1, x1)])

    while q:
        y, x = q.popleft()
        for dy, dx in zip(ddy, ddx):
            for j in range(1, K+1):
                if not (0<=y+dy*j<H and 0<=x+dx*j<W):
                    break
                if l[y+dy*j][x+dx*j]:
                    break

                if dist[(y+dy*j, x+dx*j)] > dist[(y, x)] + 1:
                    dist[(y+dy*j, x+dx*j)] = dist[(y, x)] + 1
                    q.append((y+dy*j, x+dx*j))
                elif dist[(y+dy*j, x+dx*j)] == dist[(y, x)] + 1:
                    continue
                else:
                    break


    ans = dist[(y2, x2)]
    print(ans if ans!=INF else -1)


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

s=input()
N=len(s)
kyonen=2019
modlist=[int(s[-1])%kyonen]
t=0
for i in range(2,N+1):
    modlist.append((modlist[-1]+(int(s[(-1)*i])*10**(i-1))%kyonen)%kyonen)
modlist.sort()
now=modlist[0]
nowc=1
ans=0
if modlist[0]==0:
    ans+=1
for i in range(1,N):
    if modlist[i]==0:
        ans+=1
    if modlist[i]==now:
        nowc+=1
    else:
        if nowc>=2:
            ans+=int(nowc*(nowc-1)/2)
        nowc=1
        now=modlist[i]

if nowc>=2:
    ans+=int(nowc*(nowc-1)/2)

print(ans)

### FIXED CODE ###

s=input()
N=len(s)
kyonen=2019
ans=0

#alistつくる
alist=[]
for i in reversed(range(N)):
    alist.append((int(s[i])*pow(10,(N-1-i),kyonen))%kyonen)

#累積和とる
ruisekiwa=[0]
for i in range(N):
    ruisekiwa.append((ruisekiwa[-1]+alist[i])%kyonen)

#累積和リストの中から、同じ数字の組み合わせの個数を求める
kazoe=[0]*2019
for i in range(N+1):
    kazoe[ruisekiwa[i]]+=1

for i in range(2019):
    if kazoe[i]>=2:
        ans+=int(kazoe[i]*(kazoe[i]-1)/2)

if ruisekiwa[N]==0:
    ans+=1

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

import copy
N = int(input())
S = input()

S_set = {S[0:3]}
for i in range(3,N):
    S_0_set = set()
    for s_0 in S_set:
        for j in range(len(s_0)):
            S_0_set.add(s_0[0:j]+s_0[j+1:3]+S[i])
    S_set = S_set.union(S_0_set)

print(len(S_set))


### FIXED CODE ###

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

def judge(S,A): #A:3桁ｎ数字
    dig,pt = 0,0
    while dig < 3 and pt < N:
        if S[pt] == A[dig]:
            dig += 1
            pt += 1
        else:
            pt += 1
        if dig == 3:
            break

    if dig == 3:
        return True
    else:
        return False

count = 0
for a in range(10):
    for b in range(10):
        for c in range(10):
            if judge(S,[str(a),str(b),str(c)]):
                count += 1

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

import math as m
n = int(input())


for i in range(1,n+1):
    c = 0
    for x in range(1,m.ceil(m.sqrt(i))):
        for y in range(1,m.ceil(m.sqrt(i-x**2))):
            for z in range(1,m.ceil(m.sqrt(i-x**2-y**2))):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
                    c +=1 
    print(c)



### FIXED CODE ###

import math as m


n = int(input())

l = [0] * 10000

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            ans = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if  ans <= 10000:
                l[ans-1] += 1

for i in range(n):
    print(l[i])
### BUGGY CODE ###

N, K = list(map(int, input().split()))
P = list(map(lambda x: (int(x) * (int(x) + 1)) / 2 / int(x), input().split()))
#print(P)
ans = 0
for i in range(N - K + 1):
  tmp = 0
  for j in range(i, i + K):
    tmp += P[j]
  if tmp > ans:
    ans = tmp
print(ans)

### FIXED CODE ###

N, K = list(map(int, input().split()))
P = list(map(lambda x: (int(x) * (int(x) + 1)) / 2 / int(x), input().split()))
#print(P)
ans = sum(P[:K])
tmp = ans
#print(ans)
for i in range(1, N - K + 1):
  tmp = tmp - P[i - 1] + P[i + K - 1]
  #print(tmp, P[i - 1], P[i + K - 1])
  if tmp > ans:
    ans = tmp
print(ans)
### BUGGY CODE ###

import sys
import numpy as np

from collections import deque 
from functools import reduce

# input = sys.stdin.readline

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

p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

list.sort(p, reverse=True)
list.sort(q, reverse=True)
list.sort(r, reverse=True)

p_np = np.zeros(999999)
q_np = np.zeros(999999)

if len(p) > x:
    p_np[:x] = p[:x]
else:
    p_np[:len(p)] = p[:]

if len(q) > y:
    q_np[:y] = q[:y]
else:
    q_np[:len(q)] = q[:]    

ap_np = np.hstack((p_np[:x], q_np[:y]))
ap_np.sort()
ap_cnt = 0

for i, ri in enumerate(r):
    for api in range(ap_cnt, x+y):
        if (r[i] > ap_np[api]):
            ap_np[api] = r[i]
            ap_cnt += 1
            break
print(int(ap_np.sum()))

### FIXED CODE ###

import sys
import numpy as np

from collections import deque 
from functools import reduce

# input = sys.stdin.readline

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

p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

list.sort(p, reverse=True)
list.sort(q, reverse=True)
list.sort(r, reverse=True)

p_np = np.zeros(999999)
q_np = np.zeros(999999)

if len(p) > x:
    p_np[:x] = p[:x]
else:
    l_p = len(p)
    p_np[:l_p] = p[:]

if len(q) > y:
    q_np[:y] = q[:y]
else:
    l_q = len(q)
    q_np[:l_q] = q[:]
ap_np = np.hstack((p_np[:x], q_np[:y]))
ap_np.sort()
ap_cnt = 0

for i, ri in enumerate(r):
    if i >= x + y:
        break
    if (r[i] > ap_np[i]):
        ap_np[i] = r[i]
print(int(ap_np.sum()))
### BUGGY CODE ###

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

for i in range(1, N+1):
    print(A.index(i)+1, end=' ')

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
rev = [0] * N
for i in range(N):
    rev[A[i]-1] = i+1
print(*rev)
### BUGGY CODE ###

import math

n = int(input())
dp = [[[0 for x in range(n + 2)] for y in range(n + 2)] for z in range(n + 2)]

for i in range(1, n + 1):
    cnt = 0
    f = int(math.sqrt(n)) + 1
    for x in range(1, f):
        for y in range(1, f):
            for z in range(1, f):
                if dp[x][y][z] > 0:
                    if dp[x][y][z] == i:
                        cnt += 1
                else:
                    dp[x][y][z] = (x ** 2) + (y ** 2) + (z ** 2) + (x * y) + (y * z) + (z * x)
                    if dp[x][y][z] == i:
                        cnt += 1
    print(cnt)

### FIXED CODE ###

import math

n = int(input())
ans = [0] * (n+1)

f = int(math.sqrt(n)) + 1
for x in range(1, f):
    for y in range(1, f):
        for z in range(1, f):
            v = (x ** 2) + (y ** 2) + (z ** 2) + (x * y) + (y * z) + (z * x)
            if v < n + 1:
                ans[v] += 1
            
for i in range(n):
    print(ans[i+1])
### BUGGY CODE ###

import re

n = int(input())
s = input()

numbers = set()

def exists(i, j, k, s):
  pattern = '.*' + str(i) + '.*' + str(j) + '.*' + str(k) + '.*'
  result = re.match(pattern, s)
  return result is not None

for i in range(0, 10):
  for j in range(0, 10):
    for k in range(0, 10):
      if exists(i, j, k, s):
        numbers.add(str(i) + str(j) + str(k))

# print(numbers)
print(len(numbers))


### FIXED CODE ###

n = int(input())
s = list(map(int, list(input())))

ary1 = [0 for i in range(10)]
ary2 = [[0 for i in range(10)] for j in range(10)]
ary3 = [[[0 for i in range(10)] for j in range(10)] for k in range(10)]

for ss in s:
  for i in range(10):
    for j in range(10):
      if ary1[i] == 1 and ary2[i][j] == 1:
        ary3[i][j][ss] = 1
  for i in range(10):
    if ary1[i] == 1:
      ary2[i][ss] = 1
  ary1[ss] = 1

numbers = set()

def exists(i, j, k, s):
  return ary3[i][j][k] == 1

for i in range(0, 10):
  for j in range(0, 10):
    for k in range(0, 10):
      if exists(i, j, k, s):
        numbers.add(str(i) + str(j) + str(k))

# print(numbers)
print(len(numbers))
### BUGGY CODE ###

n,v=[int(k) for k in input().split()]
li=[]
for i in range(n):
  li.append([int(k) for k in input().split()])
  
dp=[[0 for i in range(v+1)] for j in range(n+1)]
for a in range(1,n+1):
  for b in range(1,v+1):
    if(li[a-1][0]<=b):
      dp[a][b]=max(li[a-1][1]+dp[a-1][b-li[a-1][0]],dp[a-1][b])
    else:
      dp[a][b]=dp[a-1][b]
print(dp[n][v])      
      
  


### FIXED CODE ###

n,v=[int(k) for k in input().split()]
li=[]
for i in range(n):
  li.append([int(k) for k in input().split()])
  
dp=[[0 for i in range(v+1)] for j in range(n+1)]
for a in range(1,n+1):
  for b in range(1,v+1):
    if(li[a-1][0]<=b):
      dp[a][b]=max(li[a-1][1]+dp[a-1][b-li[a-1][0]],dp[a-1][b])
    else:
      dp[a][b]=dp[a-1][b]
print(dp[n][v])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
count = [0] * 60
m = 1000000007
def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K = (K * x) % 1000000007
        x = (x * x) % 1000000007
        n //= 2
    return (K * x) % 1000000007
mul = [pow_k(2,59-i) for i in range(60)]
for a in A:
    b = bin(a)
    for i in range(1,len(b)-1):
        if b[-i] == '1':
            count[-i] += 1
print(sum([count[i]*(N-count[i])*mul[i]%m for i in range(60)])%m)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
count = [0] * 60
m = 1000000007
def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K = (K * x) % 1000000007
        x = (x * x) % 1000000007
        n //= 2
    return (K * x) % 1000000007
mul = [pow_k(2,59-i) for i in range(60)]
for a in A:
    b = bin(a)
    for i in range(1,len(b)-1):
        if b[-i] == '1':
            count[-i] += 1
print(sum([count[i]*(N-count[i])*mul[i]%m for i in range(60)])%m)
### BUGGY CODE ###

N = int(input())
ans = 0
for j in range(1,N+1):
    for i in range(1,N+1):
        if i % j == 0 :
            ans += i
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1, int(n ** 0.5) + 1):
    k = n // i
    ans += i * k * (k + 1) // 2
    if i != k:
        l = n // (i + 1)
        ans += i * (i + 1) * (k + l + 1) * (k - l) // 4
print(ans)
### BUGGY CODE ###

import numpy as np
m = 10**9 + 7
n = int(input())
an = list(map(int, input().split()))
an_np = np.array(an)
summary = 0
for i in range(0, n-1):
    summary = (summary + sum(np.multiply(an_np[i], an_np[i+1: n]) % m)) % m    
print(summary)

### 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 ###

n=int(input())
a=list(map(int,input().split()))
ans=float('inf')
for i in range(1,n):
    s1=sum(a[0:i])
    s2=sum(a[i:])
    ans=min(ans,abs(s1-s2))
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=float('inf')
s=sum(a)
s1 = a[0]
s2 = s-s1
ans = min(ans, abs(s1 - s2))
for i in range(1,n):
    s1+=a[i]
    s2-=a[i]
    ans = min(ans, abs(s1 - s2))

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

import re

N,Q = map(int, input().split())
S = input()
for _ in range(Q):
    l,r = map(int, input().split())
    s = S[l-1:r]
    ans = s.count('AC')
    print(ans)



### 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 ###

N = int(input())
flag = 0
for a in range(1,3501):
    if flag == 1:
        break
    for b in range(1,1751):
        M = (4*a*b - N*a - N*b)
        C = N*a*b
        if M < 0 :
            continue
        elif M != 0:
            if C//M == C/M:
                c = C//M
                print(a,b,c)
                flag = 1
                break

### FIXED CODE ###

import sys
N = int(input())
for h in range(1,3501):
    for n in range(1,3501):
        if 4*n*h > N*n + N*h and (N*n*h) % (4*n*h-N*h-N*n) == 0:
            w =  (N*n*h) // (4*n*h-N*h-N*n)
            print(n,h,w)
            sys.exit()
### BUGGY CODE ###

def  XYZTriplets():

    num = int(input())
    
    for i in range(num):
        count = 0

        x = 1
        y = 1
        z = 1

        flag = True
        
        while flag == True:
            
            function = 0.5*( (x+y)*(x+y) + (y+z)*(y+z) + (z+x)*(z+x) ) - i
                        
            if function == 0:
                if x == y and y == z and z == x:
                    count = count + 1
                
                else:
                    count = count + 3
            
                list_xyz = [x, y, z]
            
                if list_xyz.index(max(list_xyz)) == 0:
                    x = x + 1
                elif list_xyz.index(max(list_xyz)) == 1:
                    y = y + 1
                else:
                    z = z + 1
            
            if function > 0:
                print(count)
        
                break



if __name__ == '__main__':
    XYZTriplets()


### FIXED CODE ###

import math
import numpy as np

def  XYZTriplets():

    num = int(input())
    
    list_num = []
    
    count = [0]*num
    
    for i in range(1, num+1):
        list_num.append(i)

    for x in range(1, int(math.sqrt(num))):
        for y in range(1, int(math.sqrt(num))):
            for z in range(1, int(math.sqrt(num))):
                
                function = x*x + y*y + z*z + x*y + y*z + z*x
                
                if function <= num and function > 0:
                    count[function-1] = count[function-1] + 1
 
    for i in range(0, num):
        print(count[i])
        

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

import numpy as np

n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))

a  = np.sort(np.array(a))
f = np.sort(np.array(f))[::-1]

l ,r = 0, 10 ** 12
x = 0
while l <= r:
	x = (l + r) // 2
	if np.clip(a - f // x, 0, None).sum() <= k:
		l += 1
	else:
		r -= 1
print(l)

### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))

a  = np.sort(np.array(a))
f = np.sort(np.array(f))[::-1]

l ,r = 0, 10 ** 12
while l <= r:
 x = (l + r) // 2
 if np.clip(a - x // f, 0, None).sum() <= k:
  r = x - 1
 else:
  l = x + 1
print(l)
### BUGGY CODE ###

n=int(input())
c=[int(input()) for _ in range(n)]
x=[c[0]]
for i in range(1,n):
    if c[i]!=c[i-1]:
        x.append(c[i])
#print(x)

dp=[0 for _ in range(n)]
res=[[] for _ in range(max(x)+1)]
res[x[0]].append(0)
for i in range(1,len(x)):
    if len(res[x[i]])>0:
        if res[x[i]][-1]==0:#左端スタートで１つ目の場合
            dp[i]=dp[i-1]+1
        else:
            dp[i]=dp[i-1]+len(res[x[i]])
            for t in res[x[i]]:
                if t>0:
                    dp[i]+=dp[t-1]
    else:
        dp[i]=dp[i-1]
    res[x[i]].append(i)
#print(dp)
print((dp[len(x)-1]+1)%(10**9+7))
#print(res)

### FIXED CODE ###

n=int(input())
c=[int(input()) for _ in range(n)]
x=[c[0]]
for i in range(1,n):
    if c[i]!=c[i-1]:
        x.append(c[i])
#print(x)

dp=[0 for _ in range(n)]
res=[[] for _ in range(max(x)+1)]
res[x[0]].append(0)
res2=[0 for _ in range(max(x)+1)]
for i in range(1,len(x)):
    if len(res[x[i]])>0:
        if res[x[i]][-1]==0:#左端スタートで１つ目の場合
            dp[i]=dp[i-1]+1
        else:
            dp[i]=dp[i-1]+len(res[x[i]])+res2[x[i]]
            #print(res2[x[i]])
    else:
        dp[i]=dp[i-1]
    res[x[i]].append(i)
    res2[x[i]]+=dp[i-1]
    #print(dp,res2)
print((dp[len(x)-1]+1)%(10**9+7))
#print(res)
### BUGGY CODE ###

A, B, C, D = map(int,input().split())

d=[[0 for j in range(D+1)] for i in range(C+1)]
d[A][B]=1
for i in range(A+1,C+1):
  d[i][B] = B*d[i-1][B] % 998244353
for j in range(B+1,D+1):
  d[A][j] = A*d[A][j-1] % 998244353
 
for i in range(A+1,C+1):
  for j in range(B+1,D+1):
    d[i][j]=(j*d[i-1][j]) % 998244353 + i*d[i][j-1] % 998244353 -((i-1)*(j-1)*d[i-1][j-1]) % 998244353
    
print(d[C][D] % 998244353)

### FIXED CODE ###

import sys
import numpy as np
#from functools import lru_cache
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
MOD = 998_244_353
 
def main(A, B, C, D):
	d = np.zeros((C + 1, D + 1), np.int64)
	d[A,B]=1
	for i in range(A+1,C+1):
  		d[i,B] = B*d[i-1,B] % MOD
	for j in range(B+1,D+1):
		d[A,j] = A*d[A,j-1] % MOD
 
	for i in range(A+1,C+1):
		for j in range(B+1,D+1):
			d[i,j]=((((j*d[i-1,j]) % MOD + i*d[i,j-1] % MOD) % MOD) -((i-1)*((j-1)*d[i-1,j-1] % MOD)% MOD)% MOD)
    
	return d[C,D] % MOD
          
"""    
    print(d[C][D] % MOD)
    dp = np.zeros((C + 1, D + 1), np.int64)
    dp[C, D] = 1
    for d in range(D, 0, -1):
        dp[C, d - 1] = dp[C, d] * C % MOD
    for c in range(C - 1, -1, -1):
        x = 0
        for d in range(D, -1, -1):
            dp[c, d] = (d * dp[c + 1, d] + x) % MOD
            x += dp[c + 1, d]
            x *= c
            x %= MOD
    return dp[A, B]
"""

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.from_dtype(np.int64)
    signature = (i8, i8, i8, i8)
 
    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()
 
from my_module import main
 
A, B, C, D = map(int, read().split())
print(main(A, B, C, D))
### BUGGY CODE ###

t1,t2=map(int,input().split())
a1,a2=map(int,input().split())
b1,b2=map(int,input().split())
if a1==b1 and b2==a2:print(0)
elif t1*(a1-b1)+t2*(-b2+a2)==0:print('infinity')
else:
    if t1*(a1-b1)+t2*(-b2+a2)<0:a1,a2,b1,b2=b1,b2,a1,a2
    if t1*(a1-b1)>0:print(0)
    else:
        #(ng,ok]type
        ok,ng=10**300000,-1
        ng,ok=ok,ng
        eps=10**(-8)
        while abs(ok-ng)>1:
            mid=(ok+ng)//2
            if t1*(b1-a1)-mid>=0:ok=mid
            else:ng=mid
        print(2*(mid//(t1*(a1-b1)+t2*(-b2+a2))+1)-1)

### FIXED CODE ###

t1,t2=map(int,input().split())
a1,a2=map(int,input().split())
b1,b2=map(int,input().split())
p=a1-b1
q=a2-b2
if p*t1+q*t2==0:print('infinity');exit()
elif p<0:p,q=-p,-q
#p>0
if p*t1+q*t2>0:print(0)
else:
    a=p*t1
    d=-(a+q*t2)
    print(2*(a//d)+int(not(not a%d)))
### BUGGY CODE ###

n = int(input())
alist = []
for i in range(n):
    alist.append(int(input()))
mod = 998244353
asum = sum(alist)


dp = [[0] * ((asum+1)//2 + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    for j in range((asum+1)//2 + 1):
        dp[i+1][j] = (dp[i+1][j] + dp[i][j] * 2) % mod
        jsum = min(j + alist[i], (asum+1)//2)
        dp[i+1][jsum] = (dp[i+1][jsum] + dp[i][j]) % mod
dp_sum = dp[n][((asum+1)//2)] % mod
dp_sum *= 3
dp_sum = dp_sum % mod


dp_dup = [[0] * (asum + 1) for _ in range(n + 1)]
dp_dup[0][0] = 1
if asum % 2 == 0:
    for i in range(n):
        for j in range(asum // 2 + 1):
            dp_dup[i+1][j] = (dp_dup[i+1][j] + dp_dup[i][j]) % mod
            jsum = j + alist[i]
            if jsum > asum:
                continue
            dp_dup[i+1][jsum] = (dp_dup[i+1][jsum] + dp_dup[i][j]) % mod
dp_dup_sum = dp_dup[n][(asum+1)//2]
dp_dup_sum *= 3
dp_dup_sum = dp_dup_sum % mod


ans = pow(3, n, mod)
ans -= dp_sum
ans += dp_dup_sum

print(ans % mod)


### FIXED CODE ###

n = int(input())
alist = []
for i in range(n):
    alist.append(int(input()))
mod = 998244353
asum = sum(alist)


asum_half = (asum + 1) // 2
dp = [[0] * (asum_half + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    for j in range(asum_half + 1):
        inext = i + 1
        dp[inext][j] = (dp[inext][j] + dp[i][j] * 2) % mod
        jsum = min(j + alist[i], asum_half)
        dp[inext][jsum] = (dp[inext][jsum] + dp[i][j]) % mod
dp_sum = dp[n][asum_half] % mod
dp_sum *= 3
dp_sum = dp_sum % mod


dp_dup = [[0] * (asum_half + 1) for _ in range(n + 1)]
dp_dup[0][0] = 1
if asum % 2 == 0:
    for i in range(n):
        for j in range(asum_half + 1):
            inext = i + 1
            dp_dup[inext][j] = (dp_dup[inext][j] + dp_dup[i][j]) % mod
            jsum = j + alist[i]
            if jsum > asum_half:
                continue
            dp_dup[inext][jsum] = (dp_dup[inext][jsum] + dp_dup[i][j]) % mod
dp_dup_sum = dp_dup[n][asum_half]
dp_dup_sum *= 3
dp_dup_sum = dp_dup_sum % mod


ans = pow(3, n, mod)
ans -= dp_sum
ans += dp_dup_sum

print(ans % mod)
### BUGGY CODE ###

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

def solve(N: int, S: "List[str]"):

    d = defaultdict(int)
    for s in S:
        d[s]+=1

    return '\n'.join(sorted([kv[0] for kv in d.items() if kv[1] == max(d.values())]))


# Generated by 1.1.6 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
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    print(solve(N, S))

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def solve(N: int, S: "List[str]"):
    d = defaultdict(int)
    cnt_common = 0
    commons = []

    for s in S:
        d[s] += 1
        if cnt_common < d[s]:
            cnt_common=d[s]
            commons = [s]
        elif cnt_common == d[s]:
            commons.append(s)

    return '\n'.join(sorted(commons))

# Generated by 1.1.6 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
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    print(solve(N, S))

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

N=int(input())
L=list(map(int,input().split()))
L_i=[i+1 for i in range(len(L))]

cnt=0
for i in range(N):
    P_L= [m+L[i] for m in L[i:]]
    P_L_i = [x - y for (x, y) in zip(L_i[i:],[L_i[i]] * len(L_i[i:]))]
    X = sum([int(w==z) for (w, z) in zip(P_L,P_L_i)])
    cnt = cnt + X
    
print(cnt)

### FIXED CODE ###

def main():
    N=int(input())
    L=list(map(int,input().split()))
    L_i,L_j=[],[]
    L_memo = [0]*N
    cnt=0
    for i, j in enumerate(L):
        if i+j<N:
            L_memo[i+j]+=1
        if i-j>0:
            cnt+=L_memo[i-j]        
    print(cnt)
main()