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

n,k=map(int,input().split())
s=0
if k%2==0:
    l=k//2
    for a in range(1,n+1):
        if a%k==0:
            for b in range(1,n+1):
                if b%k==0:
                    for c in range(1,n+1):
                        if c%k==0:
                            s+=1
        elif a%k==l:
            for b in range(1,n+1):
                if b%k==l:
                    for c in range(1,n+1):
                        if c%k==l:
                            s+=1
else:
    for a in range(1,n+1):
        if a%k==0:
            for b in range(1,n+1):
                if b%k==0:
                    for c in range(1,n+1):
                        if c%k==0:
                            s+=1
print(s)


### FIXED CODE ###

n,k=map(int,input().split())
s=0
if k%2==0:
    s0=0
    for i in range(1,n+1):
        if i%k==0:
            s0+=1
    s1=0
    for i in range(1,n+1):
        if i%k==k//2:
            s1+=1
    s=s0**3+s1**3
else:
    s0=0
    for i in range(1,n+1):
        if i%k==0:
            s0+=1
    s=s0**3
print(s)
### BUGGY CODE ###

dxys = [(-1,0), (1,0), (0,-1), (0,1)]

H, W, K = map(int, input().split())
Ass = [input() for _ in range(H)]

def find2D(Sss, ch):
    for x, Ss in enumerate(Sss):
        y = Ss.find(ch)
        if y != -1:
            return (x, y)
    return (-1, -1)

xS, yS = find2D(Ass, 'S')

usedss = [[False]*(W) for _ in range(H)]
usedss[xS][yS] = True
vs = set([(xS, yS)])
for _ in range(K):
    v2s = set()
    for x, y in vs:
        for dx, dy in dxys:
            x2, y2 = x+dx, y+dy
            if not (0 <= x2 <= H-1 and 0 <= y2 <= W-1): continue
            if not usedss[x2][y2] and Ass[x2][y2] == '.':
                usedss[x2][y2] = True
                v2s.add((x2, y2))
    vs = v2s

ans = 10**5
for x in range(H):
    for y in range(W):
        if usedss[x][y]:
            dist = min(x, H-1-x, y, W-1-y)
            ans = min(ans, -(-dist//K)+1)

print(ans)


### FIXED CODE ###

def solve():
    dxys = [(-1,0), (1,0), (0,-1), (0,1)]

    H, W, K = map(int, input().split())
    Ass = ['#'*(W+2)] + ['#'+input()+'#' for _ in range(H)] + ['#'*(W+2)]

    def find2D(Sss, ch):
        for x, Ss in enumerate(Sss):
            y = Ss.find(ch)
            if y != -1:
                return (x, y)
        return (-1, -1)

    xS, yS = find2D(Ass, 'S')

    usedss = [[False]*(W+2) for _ in range(H+2)]
    usedss[xS][yS] = True
    vs = set([(xS, yS)])
    for _ in range(K):
        v2s = set()
        for x, y in vs:
            for dx, dy in dxys:
                x2, y2 = x+dx, y+dy
                if not usedss[x2][y2] and Ass[x2][y2] == '.':
                    usedss[x2][y2] = True
                    v2s.add((x2, y2))
        vs = v2s

    ans = 10**5
    for x in range(H):
        for y in range(W):
            if usedss[x+1][y+1]:
                dist = min(x, H-1-x, y, W-1-y)
                ans = min(ans, -(-dist//K)+1)
    print(ans)

solve()
### BUGGY CODE ###

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

result = 0
for i in range(N):
    result += A[i] * sum(A[i+1:]) % (10**9 + 7)
print(result % (10**9 + 7))


### FIXED CODE ###

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

A_sum = sum(A)
result = 0
for i in range(N):
    A_sum -= A[i]
    result += A[i] * A_sum % (10**9 + 7)
print(result % (10**9 + 7))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = 0
onaji = 0

for i in range(len(A)):
    if i >= len(A)-1:
        break
    for j in range(len(A)-1,i,-1):
        if A[i] == A[j]:
            onaji = 1
        if A[j] % A[i] == 0:
            del A[j]
            
    if onaji == 1:
        del A[i]
        onaji = 0

print(len(A))


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
OKlist = [0]*(10**6+100)
A.sort()
for i in range(len(A)-1):
    if A[i] == A[i+1]:
        OKlist[A[i]] += 1
    else:
        for j in range(10**6+10):
            if A[i]*j > 10**6:
                break
            else:
                OKlist[A[i]*j] += 1
OKlist[max(A)] += 1
cnt = 0
for i in A:
    if OKlist[i] == 1:
        cnt += 1
        
print(cnt)
### BUGGY CODE ###

def nCr(n,r):
  dividend = 1
  divisor = 1
  MOD = 10**9+7
  d1 = n
  for i in range(1,r+1):
    dividend *= d1
    divisor *= i
    d1 -= 1
    dividend %= MOD
    divisor %= MOD

  return (dividend * pow(divisor, MOD-2, MOD)) % MOD


N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
mod = 10**9+7

ans = 0
for i in range(K-1, N):
  ans += A[i] * nCr(i, K-1)
  ans %= mod

A = A[::-1]
for i in range(K-1, N):
  ans -= A[i] * nCr(i, K-1)
  ans %= mod

print(ans)

### FIXED CODE ###

class Combination:
  def __init__(self, n_max, mod=10**9+7):
    self.mod = mod
    self.modinv = self.make_modinv_list(n_max)
    self.fac, self.facinv = self.make_factorial_list(n_max)

  def __call__(self, n, r):
    return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

  def make_factorial_list(self, n):
    # 階乗のリストと階乗のmod逆元のリストを返す O(n)
    # self.make_modinv_list()が先に実行されている必要がある
    fac = [1]
    facinv = [1]
    for i in range(1, n+1):
      fac.append(fac[i-1] * i % self.mod)
      facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
    return fac, facinv

  def make_modinv_list(self, n):
    # 0からnまでのmod逆元のリストを返す O(n)
    modinv = [0] * (n+1)
    modinv[1] = 1
    for i in range(2, n+1):
      modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
    return modinv

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
MOD = 10**9+7

comb = Combination(10**5+1)

ans = 0
for i in range(N-K+1):
  ans -= A[i] * comb(N - i - 1, K - 1) % MOD
  ans %= MOD

A = A[::-1]
for i in range(N-K+1):
  ans += A[i] * comb(N - i - 1, K - 1) % MOD
  ans %= MOD

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

n,m = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(m)]
di = [[] for _ in range(n)]
for i in range(m):
    di[ls[i][0]-1].append(ls[i][1])
    di[ls[i][0]-1].sort()
for k in range(m):
    a = di[ls[k][0]-1].index(ls[k][1])
    print(str(ls[k][0]).rjust(6,"0")+str(a+1).rjust(6,"0"))
    


### FIXED CODE ###

n,m = map(int,input().split())
ls = [[] for _ in range(n+1)]
di = []
for i in range(m):
    a,b = map(int,input().split())
    ls[a].append([b,i+1])
for j in range(n+1):
    if ls[j] != []:
        ls[j].sort(key=lambda x :x[0])
        for k in range(len(ls[j])):
            di.append([ls[j][k][1],str(10**12+j*10**6+k+1)[1:]])
di.sort(key=lambda x :x[0])
for l in range(m):
    print(di[l][1])
### BUGGY CODE ###

n = int(input())
for i in range((2*n)+1):
    if i % 2==0 and i % n==0 and i>0:
        print(i)
        break
    else:
        continue


### FIXED CODE ###

n = int(input())
if n % 2 ==0:
    print(n)
else: 
    print(2*n)
### BUGGY CODE ###

import numpy as np

DIVS = 1000000007
def LI(): return [int(x) for x in input().split()]

N,M=LI()
SS=LI()
TT=LI()

dp=np.zeros((N+1, M+1), dtype=np.int)

for i in range(1,N+1):
    for j in range(1,M+1):
        if SS[i-1] != TT[j-1]:
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
        else:
            dp[i][j] = (dp[i-1][j] + dp[i][j-1] + 1) % DIVS

print((dp[N][M]+1)%DIVS)

### FIXED CODE ###

DIVS = 1000000007
def LI(): return [int(x) for x in input().split()]

N,M=LI()
SS=LI()
TT=LI()

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

for i in range(1,N+1):
    for j in range(1,M+1):
        if SS[i-1] != TT[j-1]:
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
        else:
            dp[i][j] = (dp[i-1][j] + dp[i][j-1] + 1) % DIVS

print((dp[N][M]+1)%DIVS)
### BUGGY CODE ###

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

from heapq import heappush, heappop

N,M,S = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
m = map(int,read().split())
CD = list(zip(m,m))

graph = [[] for _ in range(N)]
for u,v,a,b in ABC:
    graph[u-1].append((v-1,a,b))
    graph[v-1].append((u-1,a,b))

def f(p):
  INF = 10 ** 18
  ans = INF
  qq = 2500
  dist = [[INF] * qq for _ in range(N)]
  dist[0][min(qq-1,S)] = 0
  q = [(0,min(qq-1,S),0)]
  while q:
      st,ss,v = heappop(q) # 総時間、銀貨、今いる頂点
      if dist[v][ss] < st:
        continue
      if v == p:
        ans = st
        break
      c,d = CD[v]
      # 銀貨の購入
      if ss < qq-1:
          ns = min(ss + c, qq-1)
          nt = st + d
          if dist[v][ns] > nt:
              dist[v][ns] = nt
              heappush(q,(nt,ns,v))
      # 移動
      for nex,g,tt in graph[v]:
          if ss-g < 0:
              continue
          dt = st + tt
          if dist[nex][ss-g] <= dt:
              continue
          dist[nex][ss-g] = dt
          heappush(q,(dt,ss-g,nex))
  return ans
      
for i in range(1,N):
  answer = f(i)
  print(answer)

### FIXED CODE ###

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

from heapq import heappush, heappop

N,M,S = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
m = map(int,read().split())
CD = list(zip(m,m))

graph = [[] for _ in range(N)]
for u,v,a,b in ABC:
    graph[u-1].append((v-1,a,b))
    graph[v-1].append((u-1,a,b))

def f():
  INF = 10 ** 18
  arrive = [False]*N
  ans = []
  qq = 2500
  dist = [[INF] * qq for _ in range(N)]
  dist[0][min(qq-1,S)] = 0
  q = [(0,min(qq-1,S),0)]
  while q:
      st,ss,v = heappop(q) # 総時間、銀貨、今いる頂点
      if dist[v][ss] < st:
        continue
      if not arrive[v]:
        arrive[v] = True
        ans.append((v,st))
        if all(arrive):
          break
      c,d = CD[v]
      # 銀貨の購入
      if ss < qq-1:
          ns = min(ss + c, qq-1)
          nt = st + d
          if dist[v][ns] > nt:
              dist[v][ns] = nt
              heappush(q,(nt,ns,v))
      # 移動
      for nex,g,tt in graph[v]:
          if ss-g < 0:
              continue
          dt = st + tt
          if dist[nex][ss-g] <= dt:
              continue
          dist[nex][ss-g] = dt
          heappush(q,(dt,ss-g,nex))
  return ans

ab = f()
from operator import itemgetter
ab = sorted(ab,key=itemgetter(0))
for i in range(1,N):
  print(ab[i][1])
### BUGGY CODE ###

n = int(input())
ns = list(map(int, input().split()))

rslt = []
ttl = sum(ns)
for i in range(n):
    rslt.append(ttl - 2 * sum(ns[i % 2:max(i - 1, 0):2] + ns[i + 1::2]))
print(*rslt)

### FIXED CODE ###

n = int(input())
ns = list(map(int, input().split()))

rslt = []
ttl = sum(ns)
x = ttl - 2 * sum(ns[i] for i in range(1, n, 2))
rslt.append(x)
for i in range(0, n-1):
    x = 2 * ns[i] - x
    rslt.append(x)
print(*rslt)
### BUGGY CODE ###

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

def main(*args, **kwargs):
    # Initialize data
    H, W = map(int, input().split())
    total_cells = H * W
    existing_black_cells = 0

    grid = []
    for i in range(H):
        line = input()
        existing_black_cells += line.count('#')
        grid.append(line)

    # Initialize Search
    queue = deque()
    queue.append((0, 0))  # start point
    visited = set()
    movement = 0

    while len(queue) > 0:
        movement += 1
        for i in range(len(queue)):  # Process same level
            coodinate = queue.popleft()
            visited.add(coodinate)
            y = coodinate[0]
            x = coodinate[1]

            # Terminate condition
            if y == H - 1 and x == W - 1:
                print(total_cells - movement - existing_black_cells)
                return

            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                X = x + dx
                Y = y + dy
                adjacent = (Y, X)
                if 0 <= X < W and 0 <= Y < H and grid[Y][X] == '.' and adjacent not in visited:
                    queue.append(adjacent)
    print(-1)
    return
main()

### FIXED CODE ###

import sys
from collections import deque
    
def main(*args, **kwargs):
    # Initialize data
    H, W = map(int, sys.stdin.readline().split())
    total_cells = H * W
    existing_black_cells = 0
 
    grid = []
    for i in range(H):
        line = sys.stdin.readline()
        existing_black_cells += line.count('#')
        grid.append(line)
 
    # Initialize Search
    queue = deque()
    queue.append((0, 0))  # start point
    visited = set()
    visited.add((0, 0))
    movement = 0
 
    while len(queue) > 0:
        movement += 1
        for i in range(len(queue)):  # Process same level
            coodinate = queue.popleft()
            y = coodinate[0]
            x = coodinate[1]
 
            # Terminate condition
            if y == H - 1 and x == W - 1:
                print(total_cells - movement - existing_black_cells)
                return
 
            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                X = x + dx
                Y = y + dy
                adjacent = (Y, X)
                if 0 <= X < W and 0 <= Y < H and grid[Y][X] == '.' and adjacent not in visited:
                    queue.append(adjacent)
                    visited.add(adjacent)
    print(-1)
    return
main()
### BUGGY CODE ###

from bisect import bisect

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

ans = float("inf")
for i in range(2, n - 1):
	former_cut = bisect(b[:i], b[i-1] / 2)
	if former_cut == 0 or b[former_cut-1] < b[i-1] - b[former_cut]:
		p, q = b[former_cut], b[i-1] - b[former_cut]
	else:
		p, q = b[former_cut-1], b[i-1] - b[former_cut-1]

	latter_cut = bisect(b, (b[-1] + b[i-1]) / 2)
	#print(latter_cut)
	if b[latter_cut-1] - b[i-1] >= b[-1] - b[latter_cut]:
		r, s = b[latter_cut-1] - b[i-1], b[-1] - b[latter_cut-1]
	else:
		r, s = b[latter_cut] - b[i-1], b[-1] - b[latter_cut]
	#print(p, q, r, s)
	ans = min(ans, max(p, q, r, s) - min(p, q, r, s))

print(ans)

### FIXED CODE ###

from bisect import bisect, bisect_left

n = int(input())
a = list(map(int, input().split()))
b = [0]
for i in range(n):
	b.append(b[-1] + a[i])

ans = float("inf")
for j in range(2, n-1):
	c = []
	f = bisect(b, b[j]/2)
	f -= 1
	if f == 0 or j == 2:
		c += [b[1]-b[0], b[j]-b[1]]
	elif f == j-1:
		c += [b[j-1]-b[0], b[j]-b[j-1]]
	else:
		if abs(b[f]-b[0] - (b[j]-b[f])) <= abs(b[f+1]-b[0] - (b[j]-b[f+1])):
			c += [b[f]-b[0], b[j]-b[f]]
		else:
			c += [b[f+1]-b[0], b[j]-b[f+1]]

	l = bisect(b, b[j]+((b[n]-b[j])/2))
	l -= 1
	#print(l)
	if l == j or j == n-2:
		c += [b[j+1]-b[j], b[n]-b[j+1]]
	elif l == n-1:
		c += [b[n-1]-b[j], b[n]-b[n-1]]
	else:
		if abs(b[l]-b[j] - (b[n]-b[l])) <= abs(b[l+1]-b[j] - (b[n]-b[l+1])):
			c += [b[l]-b[j], b[n]-b[l]]
		else:
			c += [b[l+1]-b[j], b[n]-b[l+1]]

	ans = min(ans, max(c)-min(c))

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

def exchange(n, s, d):
  v = [n] * (n + 1)
  s = [1] + s
  d = [1] + d

  for i in range(len(v) - 1):
    for a, b in zip(s, d):
      if i + a < len(v):
        v[i + a] = max(v[i] - a + b, v[i + a])

  return v[-1]


def main():
  n = int(input())
  a = list(map(int, input().split()))
  b = list(map(int, input().split()))

  n = exchange(n, a, b)
  n = exchange(n, b, a)

  print(n)


if __name__ == '__main__':
  main()


### FIXED CODE ###

def exchange(n, s, d):
  v = [n] * (n + 1)
  r = [(1, 1)] + [(a, b) for a, b in zip(s, d) if a < b]

  for i in range(len(v) - 1):
    for a, b in r:
      if i + a < len(v):
        v[i + a] = max(v[i] - a + b, v[i + a])

  return v[-1]


def main():
  n = int(input())
  a = list(map(int, input().split()))
  b = list(map(int, input().split()))

  n = exchange(n, a, b)
  n = exchange(n, b, a)

  print(n)


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

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
ii0 = lambda: ii() - 1
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')

def main():
    N,M,L = mis()
    import numpy as np
    INF = np.iinfo(np.int64).max
    d = np.full((N,N), INF, dtype=np.uint64)
    for i in range(N):
        d[i,i] = 0
    #
    for _ in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        if c <= L:
            d[a,b] = c
            d[b,a] = c
    #
    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])
    #
    d2 = np.full((N,N), INF, dtype=np.uint64)
    for i in range(N):
        d2[i, i] = 0
    for i in range(N):
        for j in range(N):
            if d[i, j] <= L:
                d2[i, j] = 1
    #
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d2[i, j] = min(d2[i, j], d2[i, k] + d2[k, j])
    #
    Q = ii()
    for _ in range(Q):
        s,t = mis()
        s -= 1
        t -= 1
        dist = d2[s,t]
        if dist == INF:
            print(-1)
        else:
            print(int(dist)-1)




main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
ii0 = lambda: ii() - 1
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')

def main():
    N,M,L = mis()
    from scipy.sparse.csgraph import floyd_warshall
    import numpy as np
    INF = np.iinfo(np.int64).max
    d = np.full((N,N), INF, dtype=np.uint64)
    for i in range(N):
        d[i,i] = 0
    #
    for _ in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        if c <= L:
            d[a,b] = c
            d[b,a] = c
    #
    '''
    for k in range(N):
        for i in range(N):
            np.minimum(d[i,:], d[i,k]+d[k,:], out=d[i,:])    
    '''
    d = floyd_warshall(d)
    #
    d2 = np.full((N,N), INF, dtype=np.uint64)
    for i in range(N):
        d2[i, i] = 0
    for i in range(N):
        for j in range(N):
            if d[i, j] <= L:
                d2[i, j] = 1
    #
    '''
    for k in range(N):
        for i in range(N):
            np.minimum(d2[i,:], d2[i,k]+d2[k,:], out=d2[i,:])    
    '''
    d2 = floyd_warshall(d2)
    #
    Q = ii()
    for _ in range(Q):
        s,t = mis()
        s -= 1
        t -= 1
        dist = d2[s,t]
        if dist == INF:
            print(-1)
        else:
            print(int(dist)-1)




main()
### BUGGY CODE ###

N, M = [ int(i) for i in input().strip().split(' ') ]
H = [ int(i) for i in input().strip().split(' ') ]

paths = [ input().strip().split(' ') for _m in range(M)]
count = 0
for n in range(1, N+1):
    is_good = True
    
    for path in paths:
        if (int(path[0]) == n) and (H[n-1] <= H[int(path[1])-1]):
            is_good = False
            break
        if (int(path[1]) == n) and (H[n-1] <= H[int(path[0])-1]):
            is_good = False
            break
    
    if is_good:
        count += 1
print(count)

### FIXED CODE ###

N, M = [ int(i) for i in input().strip().split(' ') ]
H    = [ int(i) for i in input().strip().split(' ') ]
paths = []
max_neighbor = [ 0 for _ in range(N)]

for _m in range(M):
    path = input().strip().split(' ')
    path = int(path[0]), int(path[1])
    max_neighbor[path[0]-1] = max(max_neighbor[path[0]-1], H[path[1]-1])
    max_neighbor[path[1]-1] = max(max_neighbor[path[1]-1], H[path[0]-1])
count = 0
for n in range(N):
    if max_neighbor[n] < H[n]:
        count += 1
print(count)
### BUGGY CODE ###

from bisect import bisect_left
n, m = map(int, input().split())
py = []
dict_p = {}
for i in range(m):
    p, y = map(int, input().split())
    py.append((p, y))
    if p not in dict_p.keys():
        dict_p[p] = list()

    dict_p[p].append(y)
#print(dict_p)
for values in dict_p.values():
    values.sort()

for p, y in py:
    x = bisect_left(dict_p[p], y)
    ans = "{:006}".format(p) + "{:006}".format(x+1)
    print(ans)


### FIXED CODE ###

from bisect import bisect_left
from collections import defaultdict
n, m = map(int, input().split())
py = []
dict_p = defaultdict(list)
for i in range(m):
    p, y = map(int, input().split())
    py.append((p, y))
    dict_p[p].append(y)
#print(dict_p)
for values in dict_p.values():
    values.sort()

for p, y in py:
    x = bisect_left(dict_p[p], y)
    ans = "{:006}".format(p) + "{:006}".format(x+1)
    print(ans)
### BUGGY CODE ###

import copy
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]
cost = copy.deepcopy(A)
edge = [[True for i in range(N)] for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if i != k and j != k:
                if cost[i][j] == cost[i][k]+cost[k][j]:
                    edge[i][j] = False
                if cost[i][j] > cost[i][k]+cost[k][j]:
                    cost[i][j] = cost[i][k]+cost[k][j]

if A != cost:
    print(-1)
else:
    import numpy as np
    A = np.array(A)
    edge = np.array(edge)
    print(A[edge].sum()//2)

### FIXED CODE ###

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

from scipy.sparse.csgraph import floyd_warshall as fw
import numpy as np
a = fw(A)
ans = 0
for i in range(N):
    a[i][i] = np.inf
for i in range(N):
    for j in range(i):
        if A[i][j]!=a[i][j]:
            print(-1)
            exit()
        else:
            if a[i][j] < np.min(a[i]+a[j]):
                ans += a[i][j]
print(int(ans))
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()

for i in range(q):
  l,r = map(int,input().split())
  l -= 1
  ans = 0
  for j in range(r-l-1):
    if( s[l+j:l+j+2] == "AC" ):
      ans += 1
  print(ans)

### FIXED CODE ###

n,q = map(int,input().split())
s = input()

array = [0]*len(s)

for i in range(1,len(s)):
  if( s[i-1:i+1] == "AC" ):
    array[i] = array[i-1] + 1
  else:
    array[i] = array[i-1]
      

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

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
flag = True
if n % 2 == 1:
    if a.count(0) != 1:
        flag = False
    for i in range(1, n//2+1):
        if a.count(i*2) != 2:
            flag = False
            break
    if flag:
        print(2**(n//2) % mod)
    else:
        print(0)
elif n % 2 == 0:
    for i in range(n//2):
        if a.count(i*2+1) != 2:
            flag = False
            break
    if flag:
        print(2**(n//2) % mod)
    else:
        print(0)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
flag = True
c = Counter(a)
#print(c)
if n % 2 == 1:
    if c[0] != 1:
        flag = False
    for i in range(1, n//2+1):
        if c[i*2] != 2:
            flag = False
            break
    if flag:
        print(2**(n//2) % mod)
    else:
        print(0)
elif n % 2 == 0:
    for i in range(n//2):
        if c[i*2+1] != 2:
            flag = False
            break
    if flag:
        print(2**(n//2) % mod)
    else:
        print(0)