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

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if~d[t]-I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque()
now.append([x1-1,y1-1])
dp[x1-1][y1-1]=0
#kの更新が遅い
def bfs(d):
    global h,w,k,dp,now,x2,y2
    l=len(now)
    if l==0:
        return
    dp_sub=deque()
    cand=set()
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,min(k+1,w-y)):
            if dp[x][y+j]==inf:
                dp_sub.append([x,y+j,d])
                #dp[x][y+j]=d
                cand.add((x,y+j))
                #now.append([x,y+j])
            else:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp_sub.append([x,y-j,d])
                #dp[x][y-j]=d
                cand.add((x,y-j))
                #now.append([x,y-j])
            else:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp_sub.append([x+j,y,d])
                #dp[x+j][y]=d
                cand.add((x+j,y))
                #now.append([x+j,y])
            else:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp_sub.append([x-j,y,d])
                #dp[x-j][y]=d
                cand.add((x-j,y))
                #now.append([x-j,y])
            else:
                break
    while dp_sub!=deque([]):
        e=dp_sub.popleft()
        dp[e[0]][e[1]]=e[2]
    for i in cand:
        now.append(i)
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)
### BUGGY CODE ###

A,B,C,D=map(int,input().split())
X=0
Y=A-1
for i in range(B-A+1):
    Y=Y+1
    
    if Y%C==0 or Y%D==0:
        continue
    else:
        X=X+1
print(X)


### FIXED CODE ###

import fractions
A,B,C,D=map(int,input().split())
E=C*D//fractions.gcd(C,D)
X=0
Y=0
X=A-1-(A-1)//C-(A-1)//D+(A-1)//E
Y=B-B//C-B//D+B//E
print(Y-X)
### BUGGY CODE ###

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

keys = []
for i, ((a, b), c) in enumerate(AB_C):
    key_flag = 0
    for c_i in c:
        key_flag |= 1<<(c_i-1)
    keys.append((a, key_flag))

dp = [[10**18 for _ in range(1<<N)] for _ in range(M+1)]
dp[0][0] = 0

for i, (price, flag) in enumerate(keys):
    for j in range(1<<N):
        dp[i+1][j] = min(
            dp[i+1][j],
            dp[i][j]
        )
        dp[i+1][j|flag] = min(
            dp[i+1][j|flag],
            dp[i+1][j] + price
        )

r = dp[M][(1<<N)-1]
print(-1 if r == 10**18 else r)

### FIXED CODE ###

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

keys = []
for i, ((a, b), c) in enumerate(AB_C):
    key_flag = 0
    for c_i in c:
        key_flag |= 1<<(c_i-1)
    keys.append((a, key_flag))

dp = [[10**18 for _ in range(1<<N)] for _ in range(M+1)]
dp[0][0] = 0

for i, (price, flag) in enumerate(keys):
    for j in range(1<<N):
        dp[i+1][j] = min(
            dp[i+1][j],
            dp[i][j]
        )
        dp[i+1][j|flag] = min(
            dp[i+1][j|flag],
            dp[i+1][j] + price
        )

r = dp[M][(1<<N)-1]
print(-1 if r == 10**18 else r)
### BUGGY CODE ###

def solve():
    N = int(input())
    d = [[float('inf')]*N for _ in range(N)]
    A = [list(map(int, input().split())) for _ in range(N)]
    for i in range(N):
        for j in range(N):
            d[i][j] = A[i][j]

    #三重ループ
    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])

    for i in range(N):
        for j in range(N):
            if d[i][j] < A[i][j]:
                return -1
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            ans += A[i][j]
            for k in range(N):
                if k!= i and k!=j and A[i][j]==A[i][k]+A[k][j]:
                    ans -= A[i][j]
                    break
    return ans
print(solve())
    

### FIXED CODE ###

def solve():
    N = int(input())
    d = [[float('inf')]*N for _ in range(N)]
    A = [list(map(int, input().split())) for _ in range(N)]
    for i in range(N):
        for j in range(N):
            d[i][j] = A[i][j]

    #三重ループ
    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])

    for i in range(N):
        for j in range(N):
            if d[i][j] < A[i][j]:
                return -1
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            ans += A[i][j]
            for k in range(N):
                if k!= i and k!=j and A[i][j]==A[i][k]+A[k][j]:
                    ans -= A[i][j]
                    break
    return ans
print(solve())
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for i in range(N)]
f_min = 0 
dp = [[f_min] * (W+1) for _ in range(N+1)]
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
def chmax(a,b):
    if a < b:
        return b
    else:
        return a
def main():
    # 初期条件

    for i in range(1,N+1):
        w,v = wv[i-1][0], wv[i-1][1]

        for sum_w in range(W+1):
            if sum_w - w >= 0:
                dp[i][sum_w] = chmax(dp[i][sum_w], dp[i-1][sum_w-w]+ v)
            
            dp[i][sum_w] = chmax(dp[i][sum_w],dp[i-1][sum_w])
    
    ans = 0
    for i in range(W+1):
        ans = chmax(ans,dp[N][i])
    print(ans)
            

            
 

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for i in range(N)]
f_min = 0 
dp = [[f_min] * (W+1) for _ in range(N+1)]
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
def chmax(a,b):
    if a < b:
        return b
    else:
        return a
def main():
    # 初期条件

    for i in range(1,N+1):
        w,v = wv[i-1][0], wv[i-1][1]

        for sum_w in range(W+1):
            if sum_w - w >= 0:
                dp[i][sum_w] = chmax(dp[i][sum_w], dp[i-1][sum_w-w]+ v)
            
            dp[i][sum_w] = chmax(dp[i][sum_w],dp[i-1][sum_w])
    
    ans = 0
    for i in range(W+1):
        ans = chmax(ans,dp[N][i])
    print(ans)
            

            
 

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

n=int(input())
a=list(map(int,input().split()))
ans=[]
for i in range(1,n+1):
    ans.append(a.index(i)+1)
print(*ans)

### FIXED CODE ###

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

s=list(input())
for i in range(s.count("?")):
  s[s.index("?")]="D"
print("".join(s))

### FIXED CODE ###

s=list(input())
for i in range(len(s)):
  if s[i]=="?":
    s[i]="D"
print("".join(s))
### BUGGY CODE ###

n,m,l=map(int,input().split())
abcs=[list(map(int,input().split())) for _ in range(m)]
for i in range(m):
	abcs[i][0]-=1
	abcs[i][1]-=1
inf =1234567890123456
dist = [[inf for i in range(n)] for j in range(n)]
for i in range(n):
	dist[i][i] = 0

for i in range(m):
	a=abcs[i][0]
	b=abcs[i][1]
	c=abcs[i][2]
	dist[a][b] = dist[b][a] = c

for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])

ans = [[inf for i in range(n)] for j in range(n)]
for i in range(n):
	ans[i][i]=0
for i in range(n):
	for j in range(i+1,n):
		if dist[i][j]<=l:
			ans[i][j]=ans[j][i]=1
for k in range(n):
	for i in range(n):
		for j in range(n):
			ans[i][j] = min(ans[i][j],ans[i][k]+ans[k][j])


for _ in range(int(input())):
	f,t=map(int,input().split())
	f-=1
	t-=1
	print(ans[f][t]-1 if ans[f][t]!=inf else -1)

### FIXED CODE ###

n,m,l=map(int,input().split())
abcs=[list(map(int,input().split())) for _ in range(m)]
for i in range(m):
	abcs[i][0]-=1
	abcs[i][1]-=1
inf =1234567890123456
dist = [[inf for i in range(n)] for j in range(n)]
for i in range(n):
	dist[i][i] = 0

for i in range(m):
	a=abcs[i][0]
	b=abcs[i][1]
	c=abcs[i][2]
	dist[a][b] = dist[b][a] = c

for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])

ans = [[inf for i in range(n)] for j in range(n)]
for i in range(n):
	ans[i][i]=0
for i in range(n):
	for j in range(i+1,n):
		if dist[i][j]<=l:
			ans[i][j]=ans[j][i]=1
for k in range(n):
	for i in range(n):
		for j in range(n):
			ans[i][j] = min(ans[i][j],ans[i][k]+ans[k][j])


for _ in range(int(input())):
	f,t=map(int,input().split())
	f-=1
	t-=1
	print(ans[f][t]-1 if ans[f][t]!=inf else -1)
### BUGGY CODE ###

# abc093_b.py
A, B,K = map(int,input().split())
for i,v in enumerate(range(A,B+1)):
    if i<=K-1 or B+1-A-K<=i:
        print(v)


### FIXED CODE ###

# abc093_b.py
A, B,K = map(int,input().split())
ans = []
for i in range(K):
#    print(i)
    ans.append(i+A)
    if i >(B-A-1):
        break
for i in range(K):
#    print(A-i)
#    print(i)
    ans.append(B-i)
    if i >(B-A-1):
        break
ans = list(set(ans))
ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

def main():
    N, Q = map(int, input().split())
    S = input()
    SL = [0 for _ in range(len(S) + 1)]
    for i in range(1, len(S)):
        if S[i - 1:i + 1] == 'AC':
            SL[i] = 1
    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        s = sum(SL[l:r])
        ans.append(s)
    for a in ans:
        print(a)


main()


### FIXED CODE ###

def main():
    N, Q = map(int, input().split())
    S = input()
    SL = [0 for _ in range(len(S))]
    for i in range(len(S) - 1):
        if S[i] == 'A' and S[i + 1] == 'C':
            SL[i + 1] = SL[i] + 1
        else:
            SL[i + 1] = SL[i]
    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        ans.append(SL[r - 1] - SL[l - 1])
    for a in ans:
        print(a)


main()
### BUGGY CODE ###

r, c, k = map(int, input().split())

dp = [[[0,0,0,0] for _j in range(c+1)] for _i in range(r)]
bord = [[0]*(c+1) for _i in range(r)]

for _i in range(k):
    _r, _c, _v = map(int, input().split())
    bord[_r-1][_c-1] = _v
            
for i in range(r):
    for j in range(c):
        y = max(dp[i-1][j])
        dp[i][j][0] = y
        dp[i][j][1] = y + bord[i][j]
        for x in range(1, 4):
            dp[i][j][x] = max(
                dp[i][j][x],
                dp[i][j-1][x],
                dp[i][j-1][x-1]+bord[i][j],             
            )

print(max(dp[r-1][c-1]))

### FIXED CODE ###

r, c, k = map(int, input().split())

dp = [[[0,0,0,0] for _j in range(c+1)] for _i in range(2)]
bord = [[0]*(c+1) for _i in range(r)]

for _i in range(k):
    _r, _c, _v = map(int, input().split())
    bord[_r-1][_c-1] = _v
            
for i in range(r):
    for j in range(c):
        dp[1][j][0] = max(dp[0][j])
        dp[1][j][1] = max(
            dp[1][j][0] + bord[i][j],
            dp[1][j-1][1],
            dp[1][j-1][0]+bord[i][j]
        )

        dp[1][j][2] = max(
            dp[1][j-1][2],
            dp[1][j-1][1]+bord[i][j],             
        )
        dp[1][j][3] = max(
            dp[1][j-1][3],
            dp[1][j-1][2]+bord[i][j],             
        )

    dp[0] = dp[1][::]

print(max(dp[1][c-1]))
### BUGGY CODE ###

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

import numpy as np
# from itertools import *
# from collections import *

# S = input().split()
# N = int(input().split())
# N, K = [int(x) for x in input().split()]

N, M = [int(x) for x in input().split()]

H = np.array([int(x) for x in input().split()])

Road = []
for m in range(M):
    Road.append([int(x) for x in input().split()])

Road = np.array(Road)

good = 0

for n in range(N):
    l1 = (np.ravel(Road[Road[:, 0] == n+1])-1).tolist()
    l1.extend((np.ravel(Road[Road[:, 1] == n+1])-1).tolist())
    l1 = list(set(l1))
    if len(H[l1]) == 0:
        good += 1
        continue;

    l1.remove(n)
    if max(H[l1]) < H[n]:
        good += 1

print(good)


### FIXED CODE ###

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

import numpy as np
# from itertools import *
# from collections import *

# S = input().split()
# N = int(input().split())
# N, K = [int(x) for x in input().split()]

N, M = [int(x) for x in input().split()]

H = np.array([int(x) for x in input().split()])

good = [1] * N

road = []
for m in range(M):
    a, b = [int(x) for x in input().split()]

    if H[a-1] == H[b-1]:
        good[a-1] = 0
        good[b-1] = 0
    elif H[a-1] < H[b-1]:
        good[a-1] = 0
    else:
        good[b-1] = 0

print(sum(good))
### BUGGY CODE ###

K,S=map(int,input().split())
ans=0
for x in range(K+1):
  for y in range(K+1):
    for z in range(K+1):
      if x+y+z==S:
        ans+=1
print(ans)


### FIXED CODE ###

r,g=map(int,input().split())
X=0
for i in range(r+1):
  for j in range(r+1):
    k=g-i-j
    if k>=0 and k<=r:
      X+=1
print(X)
### BUGGY CODE ###

k, s = map(int, input().split())

ans = 0
for x in range(k + 1):
  for y in range(k + 1):
    for z in range(k + 1):
      if x + y + z == s:
        ans += 1
print(ans)

### FIXED CODE ###

k, s = map(int, input().split())

ans = 0
for x in range(k + 1):
  for y in range(k + 1):
    if 0 <= s - (x + y) <= k:
      ans += 1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

A_and_i = [[a, i] for i, a in enumerate(A)]
A_and_i.sort(reverse=True)

DP = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(N):
    a, idx = A_and_i[i]

    for j in range(N):
        # 右に持っていく
        if j <= i:
            DP[i + 1][j] = max(DP[i + 1][j], DP[i][j] +
                               a * abs(N - 1 - (i - j) - idx))
            DP[i + 1][j + 1] = max(DP[i + 1][j + 1], DP[i]
                                   [j] + a * abs(idx - j))

ans = max(DP[N])
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

A_and_i = [[a, i] for i, a in enumerate(A)]
A_and_i.sort(reverse=True)

DP = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(N):
    a, idx = A_and_i[i]

    for j in range(N):
        # 右に持っていく
        if j <= i:
            DP[i + 1][j] = max(DP[i + 1][j], DP[i][j] +
                               a * abs(N - 1 - (i - j) - idx))
            DP[i + 1][j + 1] = max(DP[i + 1][j + 1], DP[i]
                                   [j] + a * abs(idx - j))

ans = max(DP[N])
print(ans)
### BUGGY CODE ###

import numpy as np

n = int(input())
a_array = np.array([int(elem) for elem in input().split(' ')])


def calculate_cumulative_sum(a_array, n):
    cumul_sum_array = np.zeros(n, dtype=np.int32)
    cumul_sum_array[0] = a_array[0]
    for i in range(1, n):
        cumul_sum_array[i] = cumul_sum_array[i - 1] + a_array[i]
    return cumul_sum_array


def check_1(cumul_sum_array):
    result = (cumul_sum_array != 0).all()
    return result


def check_2(cumul_sum_array):
    odd = np.sign(cumul_sum[::2])
    even = np.sign(cumul_sum[1::2])
    odd_sign = np.unique(odd)
    even_sign = np.unique(even)
    return (len(odd_sign) == 1) * (len(even_sign) == 1) * (odd_sign[0] != even_sign[0])


cumul_sum = calculate_cumulative_sum(a_array, n)
count = {'plus': 0, 'minus': 0}

def calc_num_manipulation(cumul_sum, start, n):
    cumul_sum = cumul_sum.copy()
    count = 0
    if check_1(cumul_sum) and check_2(cumul_sum):
        return count
    
    for i in range(n):
        if i == 0:
            diff = cumul_sum[i] - start
            count += abs(diff)
            cumul_sum[i:] -= diff
            
        else:
            c_back, c_just = cumul_sum[i - 1], cumul_sum[i]
            if c_back < 0 and c_just <= 0:
                diff = c_just - 1
                count += abs(diff)
                cumul_sum[i:] -= diff
            elif c_back > 0 and c_just >= 0:
                diff = c_just - (-1)
                count += abs(diff)
                cumul_sum[i:] -= diff
            else:
                continue
    return count

count['plus'] = calc_num_manipulation(cumul_sum, 1, n)
count['minus'] = calc_num_manipulation(cumul_sum, -1, n)
print(min(count.values()))

### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split(' ')))

def count_manipulation(a_list, start):
    assert start in (0, 1)
    sum = 0
    count = 0
    for i, a in enumerate(a_list):
        sum += a
        if i % 2 == start:
            if sum > 0:
                continue
            else:
                diff = 1 - sum
                count += diff
                sum += diff
        else:
            if sum < 0:
                continue
            else:
                diff = sum - (-1)
                count += diff
                sum -= diff
    return count

count_plus = count_manipulation(a_list, 0)
count_minus = count_manipulation(a_list, 1)
print(min(count_plus, count_minus))
### BUGGY CODE ###

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

for i in range(N):
    print(A.count(i+1))

### FIXED CODE ###

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

import collections
c=collections.Counter(A)

for i in range(N):
    print(c[i+1])
### BUGGY CODE ###

H, W, M = map(int, input().split())
h = [0] * (H+1)
w = [0] * (W+1)
l = set()
for i in range(M):
  x, y = map(int, input().split())
  h[x] += 1
  w[y] += 1
  l.add((x, y))
  
a = [i for i, x in enumerate(h) if x == max(h)]
b = [i for i, x in enumerate(w) if x == max(w)]

flag = False
for s in a:
  for t in b:
    if (s, t) not in l:
      flag = True
      break
  if flag:
    break
ans = max(h)+max(w)
if not flag:
  ans -= 1
print(ans)


### FIXED CODE ###

H, W, M = map(int, input().split())
h = [0] * (H+1)
w = [0] * (W+1)
l = set()
for i in range(M):
  x, y = map(int, input().split())
  h[x] += 1
  w[y] += 1
  l.add((x, y))
  
c = max(h)
d = max(w)
a = [i for i, x in enumerate(h) if x == c]
b = [i for i, x in enumerate(w) if x == d]

flag = False
for s in a:
  for t in b:
    if (s, t) not in l:
      flag = True
      break
  if flag:
    break
ans = c+d
if not flag:
  ans -= 1
print(ans)
### BUGGY CODE ###

import sys,math,copy
from fractions import gcd
input = sys.stdin.readline

N=int(input().strip())
A=[int(x) for x in input().strip().split()]
# def gcd(a,b):
#     if b==0:
#         return a
    
#     return gcd(b,a%b)

ANS=[]
L=[0]
R=[0]
for i in range(len(A)):
    L.append(gcd(A[i],L[i]))
    R=[gcd(A[-1-i],R[0])]+R

for i in range(len(L)-1):
    ANS.append(gcd(L[i],R[i+1]))

print(max(ANS))


### FIXED CODE ###

import sys,math,copy
from fractions import gcd
input = sys.stdin.readline

N=int(input().strip())
A=[int(x) for x in input().strip().split()]
# def gcd(a,b):
#     if b==0:
#         return a
    
#     return gcd(b,a%b)

ANS=[]
L=[0]
R=[0]
for i in range(len(A)):
    L.append(gcd(A[i],L[-1]))
    R.append(gcd(A[-1-i],R[-1]))

R.reverse()
for i in range(len(L)-1):
    ANS.append(gcd(L[i],R[i+1]))

print(max(ANS))
### BUGGY CODE ###

N = int(input())
Y = [[[] for _ in range(26)] for _ in range(10)]
# print(Y)
c = 0

for i in range(N):
    s = input()
    o = ord(s[0])-97
    l = len(s)
    if s not in Y[l-1][o]:
        Y[l-1][o].append(s)
        c += 1
# print(Y)
print(c)


### FIXED CODE ###

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

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
n,a,b=map(int,input().split())
ans=(2**n-1-cmb(n,a)-cmb(n,b))%(10**9+7)
print(ans)

### FIXED CODE ###

mod=10**9+7
n,a,b=map(int,input().split())
ans=pow(2,n,mod)-1 #n種類の花を使って花束を作る総数は2^n-1通り
comb1=1 #nCaの計算
for i in range(n-a+1,n+1): #n*(n-1)*…*(n-a+1)を計算
 comb1*=i
 comb1%=mod
for i in range(1,a+1): #1/a!=1/(1*2*…*a)=1^(p-2)*2^(p-2)*…*a^(p-2) (p=10**9+7)を計算
 comb1*=pow(i,mod-2,mod)
 comb1%=mod
comb2=1
for i in range(n-b+1,n+1): #n*(n-1)*…*(n-b+1)を計算
 comb2*=i
 comb2%=mod
for i in range(1,b+1): #1/b!=1/(1*2*…*b)=1^(p-2)*2^(p-2)*…*b^(p-2) (p=10**9+7)を計算
 comb2*=pow(i,mod-2,mod)
 comb2%=mod
ans-=(comb1+comb2) #nCa、nCbを総数から引く
ans%=mod
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
ans = 1
for i in l:
    ans *= i
if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
ans = 1
for i in l:
    ans *= i
    ans = min(ans, 10**18 + 1)

if ans == 10**18 + 1:
    ans = -1
print(ans)
### BUGGY CODE ###

alist = []
blist = []
ablist = []
N,M=map(int, input().split())
for _ in range(M):
    a,b=map(int, input().split())
    alist.append(a)
    blist.append(b)
Ndic = {1:[0,0]}
def duplistindex(list1,list2, number):
    returnlist = []
    for l in [i for i, x in enumerate(list1) if x == number]:
        returnlist.append(list2[l])
    for l in [i for i, x in enumerate(list2) if x == number]:
        returnlist.append(list1[l])
    return returnlist
reviewed = [1]
while reviewed:
    for review in reviewed:
        for i in duplistindex(alist,blist,review):
            if i not in Ndic.keys():
                Ndic[i] = []
                Ndic[i].append(Ndic[review][0] + 1)
                Ndic[i].append(review)
                reviewed.append(i)
            else:
                if Ndic[i][0] > Ndic[review][0] + 1:
                    Ndic[i][0] = Ndic[review][0] + 1
                    Ndic[i][1] = review
                    reviewed.append(i)
        reviewed.remove(review)
print('Yes')
for i in range(N-1):
    print(Ndic[i+2][1])

### FIXED CODE ###

from collections import deque
N,M=map(int, input().split())
alist = []
blist = []
T = [ [] for _ in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    T[a-1].append(b)
    T[b-1].append(a)
# T[i]にはi+1が接続してる数のリスト
rdic = [0]*(N)
d = deque()
d.append(1)
c = 0
ans = [0]*N
while len(d)>0:
    getlist = T[d[0]-1]
    for i in getlist:
        if rdic[i-1]==0:
            rdic[i-1] = d[0]
            d.append(i)
    d.popleft()
print('Yes')
for n in range(2,N+1):
    print(rdic[n-1])
### BUGGY CODE ###

import copy
import math
import string
import heapq
import bisect
import sys
sys.setrecursionlimit(10**7)

# max(a-b,b-a) < c < a+b

N = int(input())
L = list(map(int,input().split()))
L.append(2**63)
L.sort()

ans = 0;
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        l = bisect.bisect_left(L,max(L[i]-L[j],L[j]-L[i])+1)
        r = bisect.bisect_right(L,L[i]+L[j]-1)
        cnt = r-l;
        if L[l] <= L[i] < L[r]:
            cnt -= 1
        if L[l] <= L[j] < L[r]:
            cnt -= 1
        ans += cnt
print(ans//3)


### FIXED CODE ###

import copy
import math
import string
import heapq
import bisect
import sys
sys.setrecursionlimit(10**7)

# max(a-b,b-a) < c < a+b

N = int(input())
L = list(map(int,input().split()))
L.append(2**63)
L.sort()

ans = 0;
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        l = bisect.bisect_left(L,max(L[i]-L[j],L[j]-L[i])+1)
        r = bisect.bisect_right(L,L[i]+L[j]-1)
        cnt = r-l;
        if L[l] <= L[i] < L[r]:
            cnt -= 1
        if L[l] <= L[j] < L[r]:
            cnt -= 1
        ans += cnt
print(ans//3)