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

import math
def cc(m,r):
    return math.factorial(m) // (math.factorial(m - r) * math.factorial(r))
n,a,b=map(int,input().split(" "))
ans=0
for i in range(1,n+1):
  ans+=cc(n%1000000007,i)%1000000007
ans-=cc(n%1000000007,a)%1000000007
ans-=cc(n%1000000007,b)%1000000007
print(ans)

### FIXED CODE ###

from functools import reduce
def cmb(r):
    numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
    denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
    return numerator * pow(denominator, mod - 2, mod) % mod
n,a,b = map(int,(input().split()))
ans=0
mod=10**9+7

ans=pow(2,n,10**9+7)-1
ans-=cmb(a)
ans-=cmb(b)
print(ans%mod)
### BUGGY CODE ###

N,K= map(int,input().split())
A=list(map(int,input().split()))
count=0
now=1
while  count < K:
    now=A[now-1]
    count+=1
print(now)


### FIXED CODE ###

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

s = [True] * n #訪れているかを判定するlist
c = [1] #訪ずれた順番を記録するlist
now = 0 #現在地
while s[now]:
    s[now] = False #訪ずれた地点を記録
    now = a[now] - 1
    c.append(now+1)

start_cycle = c.index(c[-1]) #ループに入る点
loop = c[start_cycle:-1] #ループのlist
cycle = len(loop)

if k < start_cycle: #ループまで到達できないK
    print(c[k])
else:
    k -= start_cycle
    k %= cycle
    print(loop[k])
### BUGGY CODE ###

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


for i in range(1,n):
    s=sum(a[:i])
    if s*sum(a[:i+1])>=0:
        c+=abs(a[i]+s)+1
        if s>0:
            a[i]=-s-1
        else:
            a[i]=-s+1
print(c)

### FIXED CODE ###

n=int(input())
a=list(map(int , input().split()))
res_o=[0]*n
res_e=[0]*n
res_o[0]=a[0]
res_e[0]=a[0]

o=0
e=0

if res_o[0]<=0:
    o+=1-res_o[0]
    res_o[0]=1
if res_e[0]>=0:
    e+=res_e[0]+1
    res_e[0]=-1

for i in range(1,n):
    res_o[i]=res_o[i-1]+a[i]
    res_e[i]=res_e[i-1]+a[i]
    if i%2==0 and res_o[i]<=0:
        o+=(1-res_o[i])
        res_o[i]=1
    elif i%2==1 and res_o[i]>=0:
        o+=(res_o[i]+1)
        res_o[i]=-1
    if i%2==0 and res_e[i]>=0:
        e+=(1+res_e[i])
        res_e[i]=-1
    elif i%2==1 and res_e[i]<=0:
        e+=(1-res_e[i])
        res_e[i]=1
print(min(e,o))
### BUGGY CODE ###

n = int(input())
s = input()
W_list = []
E_list = []

for i in range(n):
    search_range = s[:i+1]
    W_list.append(search_range.count("W"))
    E_list.append(search_range.count("E"))
min = n
for i in range(n):
    if i == 0:
        change_man = E_list[-1] - E_list[0]
        if min > change_man:
            min = change_man
            continue
    left_range = W_list[i-1]
    right_range = E_list[-1] - E_list[i]
    change_man = left_range + right_range
    if min > change_man:
        min = change_man
print(min)

### FIXED CODE ###

n = int(input())
s = input()
E = s.count("E")
W = 0
min_num = n
for s_i in s:
    if s_i == "E":
        E -= 1
    else :
        W += 1

    change_man = E + W - bool(s_i == "W")
    min_num = min(min_num, change_man)
print(min_num)
### BUGGY CODE ###

import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)

b = []
for i in range(N - 1):
    x = a[i] // 2
    l = i + 1
    r = N - 1
    while r - l > 1:
        mid = l + (r - l) // 2
        if a[mid] < x:
            r = mid
        else:
            l = mid
    if abs(x - a[l]) <= abs(x - a[r]):
        b.append([a[i], a[l]])
    else:
        b.append([a[i], a[r]])

t = 0
ans = 0

for i in range(len(b)):
    tmp = combinations_count(b[i][0], b[i][1])
    if t < tmp:
        t = tmp
        ans = i

print(b[ans][0], b[ans][1])


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)

x = a[0] // 2
l = 1
r = N - 1
while r - l > 1:
    mid = l + (r - l) // 2
    if a[mid] < x:
        r = mid
    else:
        l = mid
if abs(x - a[l]) <= abs(x - a[r]):
    print(a[0], a[l])
else:
    print(a[0], a[r])
### BUGGY CODE ###

import numpy as np


N = int(input())

e = np.zeros(N + 1)
for i in range(1, N + 1):
    e[i:N+1:i] += 1
ans = 0
for i in range(1, N + 1):
    ans += i * int(e[i])
print(ans)


### FIXED CODE ###

N = int(input())

def gfunc(n):
    return int((n * (n + 1)) / 2)


ans = 0
for i in range(1, N + 1):
    ans += i * gfunc(N // i)
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
xyl = []
for _ in range(n):
    x,y = map(int,input().split())
    xyl.append((x,y))

ans = float("inf")
for i in range(n):
    for j in range(i+1, n):
        for h in range(j+1, n):
            for g in range(h+1, n):
                x1 = min(xyl[i][0], xyl[j][0], xyl[h][0], xyl[g][0])
                x2 = max(xyl[i][0], xyl[j][0], xyl[h][0], xyl[g][0])
                y1 = min(xyl[i][1], xyl[j][1], xyl[h][1], xyl[g][1])
                y2 = max(xyl[i][1], xyl[j][1], xyl[h][1], xyl[g][1])
                cnt = 0
                for p in range(n):
                    if x1 <= xyl[p][0] <= x2 and  y1 <= xyl[p][1] <= y2:
                        cnt += 1
                        if cnt == k:
                            ans = min(ans, (x2 - x1) * (y2 - y1))
                            continue


for i in range(n):
    for j in range(i+1, n):
        for h in range(j+1, n):
            x1 = min(xyl[i][0], xyl[j][0], xyl[h][0])
            x2 = max(xyl[i][0], xyl[j][0], xyl[h][0])
            y1 = min(xyl[i][1], xyl[j][1], xyl[h][1])
            y2 = max(xyl[i][1], xyl[j][1], xyl[h][1])
            cnt = 0
            for p in range(n):
                if x1 <= xyl[p][0] <= x2 and  y1 <= xyl[p][1] <= y2:
                    cnt += 1
                    if cnt == k:
                        ans = min(ans, (x2 - x1) * (y2 - y1))
                        continue

for i in range(n):
    for j in range(i+1, n):
        x1 = min(xyl[i][0], xyl[j][0])
        x2 = max(xyl[i][0], xyl[j][0])
        y1 = min(xyl[i][1], xyl[j][1])
        y2 = max(xyl[i][1], xyl[j][1])
        cnt = 0
        for p in range(n):
            if x1 <= xyl[p][0] <= x2 and  y1 <= xyl[p][1] <= y2:
                cnt += 1
                if cnt == k:
                    ans = min(ans, (x2 - x1) * (y2 - y1))
                    continue



print(ans)

### FIXED CODE ###

N, K = list(map(int, input().split()))
P = sorted([tuple(map(int, input().split())) for _ in range(N)])

ans = 1e30
for lx in range(N):
    for rx in range(lx+K, N+1):
        Q = sorted(P[lx:rx], key=lambda x:x[1])
        for ly in range(len(Q)):
            R = Q[ly:ly+K]
            if len(R)>=K: ans = min(ans, (P[rx-1][0]-P[lx][0])*(R[-1][1]-R[0][1]))
print(ans)
### BUGGY CODE ###

S, T = input(), input()

def func(S, T):
    # tの文字がsになかったら条件を満たさない
    for t in T:
        if t not in S:
            return -1

    ans = 0
    len_s = len(S)
    index = pre_index = -1

    for i in range(len(T)):
        while True:
            index += 1
            if T[i] == S[index%len_s]:
                ans += index - pre_index
                pre_index = index
                break
    return ans

print(func(S,T))


### FIXED CODE ###

S, T = input(), input()

def func(S, T):

    merge_S = list(set(S))
    merge_T = list(set(T))
    for t in merge_T:
        if t not in merge_S:
            return -1

    S_2 = S+S
    len_s = len(S)

    ans = -1

    for t in T:
        ans += S_2[(ans+1)%len_s:].index(t) + 1

    return ans + 1

print(func(S,T))
### BUGGY CODE ###

import math

def move(n):
	twonum = n // 2
	com = 0
	for i in range(twonum + 1):
		up = n - i
		com += math.factorial(up) // (math.factorial(up - i) * math.factorial(i))
	return com

N, M = map(int, input().split())
a = []
a.append(0)
for i in range(M):
	a.append(int(input()))
a.append(N+1)

s = 1
for i in range(M+1):
	step = a[i+1] - a[i] - 1
	if step > 1000000007:
		step = step % 1000000007
	m = move(step)
	s = s * m
	a[i+1] += 1

print(s % 1000000007)


### FIXED CODE ###

N, M = map(int, input().split())
a = []
for i in range(M):
	a.append(int(input()))
a.append(-1)

m = []
for i in range(N):
	if i == a[0] - 1:
		del a[0]
		m.append(0)
	elif i == 0:
		m.append(1)
	elif i == 1:
		m.append(m[0]+1)
	else:
		m.append(m[i-1]+m[i-2])

print(m[N-1] % 1000000007)
### BUGGY CODE ###

#!python3

iim = lambda: map(int, input().rstrip().split())

from bisect import bisect_left

def resolve():
    N = int(input())
    #S = [list(iim()) for i in range(N)]
    MX = 10**9
    S = []
    for i in range(N):
        x, l = iim()
        i = x - l
        if i < 0:
            i = 0
        j = x + l
        if j > MX:
            j = MX

        a = [i, j]
        S.append(a)
    S.sort()

    d = dict()
    x, y = S[0]
    d = {-1: 0}
    dk = [-1]
    ans = 0
    for x, y in S:
        for xx in dk:
            if xx <= x:
                n = d[xx] + 1
                if y in d:
                    if d[y] < n:
                        d[y] = n
                        if ans < n:
                            ans = n
                else:
                    d[y] = n
                    dk.append(y)
                    if ans < n:
                        ans = n
        #print(x, y, d)
    print(n)






if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

iim = lambda: map(int, input().rstrip().split())

from bisect import bisect_left

def resolve():
    N = int(input())
    #S = [list(iim()) for i in range(N)]
    MX = 10**9
    S = []
    for i in range(N):
        x, l = iim()
        i = x - l
        if i < 0:
            i = 0
        j = x + l
        if j > MX:
            j = MX

        a = [i, j]
        S.append(a)
    S.sort()

    ans = 0
    last = MX+1
    n = 1
    for x, y in S:
        if y < last:
            last = y
        elif last <= x:
            n += 1
            last = y

    print(n)






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

N,M = map(int,input().split())
List = []
for i in range(M):
    l,r = map(int,input().split())
    tmp = [int(i) for i in range(l,r+1)]
    List.append(tmp)
Kouho = List[0]

for i in range(1,M):
    for j in Kouho[:]:
        if not j in List[i]:
            Kouho.remove(j)
print(len(Kouho))


### FIXED CODE ###

N,M = map(int,input().split())
Max_l = 0
Min_r = float('inf')

for i in range(M):
    l,r = map(int,input().split())
    Max_l = max(Max_l,l)
    Min_r = min(Min_r,r)
ans = 0
if Max_l<=Min_r:
    ans = Min_r-Max_l+1
    

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

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
DP = [[0] * (W + 1)]
for i in range(1, N + 1):
    row = DP[i - 1][:]
    for j in range(W, -1, -1):
        new_j = j + w[i - 1]
        if 0 <= new_j <= W:
            row[new_j] = max(row[new_j], row[j] + v[i - 1])
    DP.append(row)
print(DP[-1][-1])


### FIXED CODE ###

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
DP = [[0] * (W + 1)]
for i in range(1, N + 1):
    row = DP[i - 1][:]
    for j in range(W, -1, -1):
        new_j = j + w[i - 1]
        if 0 <= new_j <= W:
            row[new_j] = max(row[new_j], row[j] + v[i - 1])
    DP.append(row)
print(DP[-1][-1])
### BUGGY CODE ###

from fractions import gcd
mod = 10**9 +7
n = int(input())
a = list(map(int, input().split()))
r = a[0]
for i in range(1, n):
    r = r*a[i]//gcd(r, a[i])
result = 0
for i in a:
    result = (result+r//i)%mod
print(result)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

mod = 10**9 + 7
memo = defaultdict(int)
base = 0
for i in a:
    base = (base+pow(i, mod-2, mod))%mod
    num = i
    for j in range(2, int(i**.5)+1):
        if num%j==0:
            c = 0
            while num%j==0:
                num //= j
                c += 1
            memo[j] = max(memo[j], c)
    if num != 1:
        memo[num] = max(memo[num], 1)
k = 1
for s, t in memo.items():
    k = (k*pow(s, t, mod))%mod

print((k*base)%mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

def dfs(v):
  if len(g[v])==0:
    dist[v]=v
  else:
    for b,d in g[v]:
      if dist[b]==10**10:
        dist[b]=dist[v]+d
        dfs(b)
      else:
        if dist[b]-dist[v]!=d:
          print('No')
          exit(0)

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
dist=[10**10]*(n+1)
for _ in range(m):
  a,b,d=map(int,input().split())
  g[a].append([b,d])
  g[b].append([a,-d])
flag=False
for i in range(1,n+1):
  if dist[i]==10**10:
    dist[i]=i
  dfs(i)
print('Yes')

### FIXED CODE ###

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)
        self.potential=[0]*(n+1)
 
    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            r = self.Find_Root(self.root[x])
            self.potential[x] += self.potential[self.root[x]]
            self.root[x]=r
            return self.root[x]
 
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y, d):
        d+=self.potential[x]-self.potential[y]
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
            self.potential[y]=d
 
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.potential[x]=-d
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
 
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def dist(self,x,y):
        if self.isSameGroup(x,y):
            return self.potential[y]-self.potential[x]
        else: return -10**10

n,m=map(int,input().split())
if m==0:
  print('Yes')
else:
  t=UnionFind(n)
  arr=[list(map(int,input().split())) for _ in range(m)]
  for l,r,d in arr:
    if t.isSameGroup(l,r) and t.dist(l,r)!=d:
      print('No')
      break
    t.Unite(l,r,d)
  else:
    print('Yes')
### BUGGY CODE ###

N = int(input())
As = [int(input()) for _ in range(N)]
result = []
for x in range(N):
  as_tmp = list(As)
  del as_tmp[x]
  result.append(max(as_tmp))
print('\n'.join(map(str, result)))

### FIXED CODE ###

N = int(input())
As = [int(input()) for _ in range(N)]
Bs = sorted(As,reverse=True)
for x in As:
  if x == Bs[0] and x != Bs[1]:
    print(Bs[1])
  else:
    print(Bs[0])
### BUGGY CODE ###

T_MAX = 10**5
n, nc = list(map(int, input().split()))
stc = [list(map(int, input().split())) for _ in range(n)]

recs = [[0]*(2*T_MAX+1) for i in range(nc)]
for i in range(n):
    s, t, c = stc[i]
    recs[c-1][2*s-1] += 1
    recs[c-1][2*t] -= 1

nrecs = [0]*(2*T_MAX+1)
for c in range(nc):
    for i in range(1, 2*T_MAX+1):
        recs[c][i] += recs[c][i-1]
        if recs[c][i] > 0:
            nrecs[i] += 1
    
print(max(nrecs))


### FIXED CODE ###

T_MAX = 10**5
n, nc = list(map(int, input().split()))
stc = [list(map(int, input().split())) for _ in range(n)]

recs = [[0]*(T_MAX+1) for c in range(nc+1)]
for s, t, c in stc:
    recs[c][s-1:t] = [1]*(t-s+1)

ans = max(map(sum, zip(*recs)))
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
L = []
for i in range(N):
    for j in range(N):
        if i+1 == A[j]:
            L.append(j+1)
print(*L)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
L = []
T = {}
for i in range(N):
    T[i+1] = A[i]
newT = {v : k for k, v in T.items()}
for i in range(1,N+1):
    L.append(newT[i])
print(*L)
### BUGGY CODE ###

N,K=map(int,input().split())
Points=[[int(i) for i in input().split()] for i in range(N)]
List_x=[Points[i][0] for i in range(N)]
List_x.sort(key=lambda x:x)
List_y=[Points[i][1] for i in range(N)]
List_y.sort(key=lambda x:x)
n=0
S=[]
for x1 in range(N-1):
  for x2 in range(x1+K-1,N):
    for y1 in range(N-1):
      for y2 in range(y1+K-1,N):
        for p in Points:
          if List_x[x1]<=p[0]<=List_x[x2] and List_y[y1]<=p[1]<=List_y[y2]:
            n+=1
        if n>=K:
          x_delta=List_x[x2]-List_x[x1]
          y_delta=List_y[y2]-List_y[y1]
          S.append(x_delta*y_delta)
        n=0
print(min(S))          
          

### FIXED CODE ###

N,K=map(int,input().split())
Points=[[int(i) for i in input().split()] for i in range(N)]
List_x=[Points[i][0] for i in range(N)]
List_x.sort(key=lambda x:x)
List_y=[Points[i][1] for i in range(N)]
List_y.sort(key=lambda x:x)
n=0
Y=0
S=[]
for x1 in range(N-1):
  for x2 in range(x1+K-1,N):
    for y1 in range(N-1):
      for y2 in range(max([y1+K-1,Y]),N):
        for p in Points:
          if List_x[x1]<=p[0]<=List_x[x2] and List_y[y1]<=p[1]<=List_y[y2]:
            n+=1
          if n==K:
            x_delta=List_x[x2]-List_x[x1]
            y_delta=List_y[y2]-List_y[y1]
            S.append(x_delta*y_delta)
            break
        if n>=K:
          n=0
          Y=y2
          break  
        n=0
    Y=0    
print(min(S))
### BUGGY CODE ###

H, W = map(int, input().split())

S = []
for i in range(H):
  S.append(list(input()))

dp1 = [[[0, 0] for w in range(W+1)] for i in range(H+1)]
for h in range(1, H+1):
  for w in range(1, W+1):
    if S[h-1][w-1] == '#':
      continue
    
    dp1[h][w] = [dp1[h-1][w][0]+1, dp1[h][w-1][1]+1]


dp2 = [[[0, 0] for w in range(W+1)] for i in range(H+1)]
for h in range(H)[::-1]:
  for w in range(W)[::-1]:
    if S[h][w] == '#':
      continue

    dp2[h][w] = [dp2[h+1][w][0]+1, dp2[h][w+1][1]+1]

ans = 0
for h in range(H):
  for w in range(W):
    ans = max(sum(dp1[h+1][w+1] + dp2[h][w])-3, ans)

print(ans)

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())

S = np.ones([H+2, W+2], dtype=bool)
for h in range(H):
  S[h+1] = np.array(['.'] + list(input()) + ['.']) == '.'

dp1 = np.zeros([H+2, W+2, 2], dtype=int) # [up, left]
for h in range(H):
  dp1[h+1, :, 0] = (dp1[h, :, 0] + 1)*S[h+1]

for w in range(W):
  dp1[:, w+1, 1] = (dp1[:, w, 1] + 1)*S[:, w+1]

dp2 = np.zeros([H+2, W+2, 2], dtype=int) # [down, right]
for h in range(H, 0, -1):
  dp2[h, :, 0] = (dp2[h+1, :, 0] + 1)*S[h]

for w in range(W, 0, -1):
  dp2[:, w, 1] = (dp2[:, w+1, 1] + 1)*S[:, w]

print(np.max((np.sum(dp1, axis=2)+np.sum(dp2, axis=2))[1:-1, 1:-1])-3)
### BUGGY CODE ###

import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
#======================================================#
def main():
    n = II()
    aa = MII()
    t = 1
    for a in aa:
        t *= a
    if t > 10**18:
        print(-1)
    else:
        print(t)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
#======================================================#
def main():
    n = II()
    aa = MII()
    t = 1
    if 0 in aa:
        print(0)
        return None
    for a in aa:
        t *= a
        if t > 10**18:
            print(-1)
            return None
    print(t)

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

N,K=map(int,input().split())
A=list(map(int,input().split()))
a=[0]*(N+1)
for i in range(N):
    a[i+1]=a[i]+A[i]
from itertools import combinations
S=[a[r]-a[l] for l,r in combinations(range(N+1),2)]
x,y=0,1<<39
for i in range(40):
    n=0
    for s in S:
        if (x+y)&s==x+y:
            n+=1
    if n>=K:
        x+=y
    y>>=1
print(x)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
a=[0]*(N+1)
for i in range(N):
    a[i+1]=a[i]+A[i]
from itertools import combinations
S=[a[r]-a[l] for l,r in combinations(range(N+1),2)]
x,y=0,1<<39
for i in range(40):
    n=0
    for s in S:
        if (x+y)&s==x+y:
            n+=1
    if n>=K:
        x+=y
    y>>=1
print(x)
### BUGGY CODE ###

N,X,Y = list(map(int,input().split()))
for i in range (1,N):
    a = max(N - 1 - (Y - X - 1) - (i - 1),0)
    if Y - X + 1 > 2 * i:
        b = Y - X + 1
        if i == 1:
            b = b - 1
    elif Y - X + 1 == 2 * i:
        b = i
    else:
        b = 0
    c = 0
    for j in range (1,X):
        if  i - (X - j) < 1:
            c = c
        elif i - (X - j)== 1:
            c = c + 1
        elif 2 * (i - (X - j)) < Y - X + 1:
            c = c + 2
        elif 2 * (i - (X - j)) == Y - X + 1:
            c = c + 1
    for j in range(Y + 1,N + 1):
        if i - (j - Y)  < 1:
            c = c
        elif i - (j - Y) == 1:
            c = c + 1
        elif 2 * (i - (j - Y)) < Y - X + 1:
            c = c + 2
        elif 2 * (i - (j - Y)) == Y - X + 1:
            c = c + 1
        
    print(a+b+c)

### FIXED CODE ###

N,X,Y = list(map(int,input().split()))
for i in range (1,N):
    a = max(N - 1 - (Y - X - 1) - (i - 1),0)
    if Y - X + 1 > 2 * i:
        b = Y - X + 1
        if i == 1:
            b = b - 1
    elif Y - X + 1 == 2 * i:
        b = i
    else:
        b = 0
    c = 0
    for j in range (max(X + 1 - i,1),X):
        if i - (X - j) == 1:
            c = c + 1
        elif 2 * (i - (X - j)) < Y - X + 1:
            c = c + 2
        elif 2 * (i - (X - j)) == Y - X + 1:
            c = c + 1
    for j in range(Y + 1,min(Y + i,N + 1)):
        if i - (j - Y) == 1:
            c = c + 1
        elif 2 * (i - (j - Y)) < Y - X + 1:
            c = c + 2
        elif 2 * (i - (j - Y)) == Y - X + 1:
            c = c + 1
        
    print(a+b+c)
### BUGGY CODE ###

from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
start = (x1-1,y1-1);goal = (x2-1,y2-1)
S=[input() for _ in range(H)]

def bfs(s):
  seen = [[0 for i in range(W)] for j in range(H)]
  d = [[0 for i in range(W)] for j in range(H)]
  todo = deque()
  now = s
  if S[now[0]][now[1]]=='@':return 0
  seen[now[0]][now[1]] = 1
  todo.append(now)
  while todo:
    now = todo.popleft()
    dx,dy = (1,-1,0,0),(0,0,1,-1)
    for i in range(4):
      for k in range(K):
        new = (now[0]+dx[i]*(k+1), now[1]+dy[i]*(k+1))
        if new[0]<0 or new[0]>=H:break
        if new[1]<0 or new[1]>=W:break
        if seen[new[0]][new[1]]==1:continue
        if S[new[0]][new[1]]=='@':break
        seen[new[0]][new[1]] = 1
        todo.append(new)
        d[new[0]][new[1]] = d[now[0]][now[1]] + 1
  return d

d = bfs(start)
print(d[goal[0]][goal[1]] if d[goal[0]][goal[1]] > 0 else -1)

### FIXED CODE ###

from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]
  INF = 10**20

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[INF for i in range(W)] for j in range(H)]
    d[x0][y0] = 0
    todo = deque()
    seen[x0][y0] = 1
    todo.append((x0,y0))
    while todo:
      x0,y0 = todo.popleft()
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if d[x][y] < d[x0][y0] + 1: break
          if S[x][y]=='@':break
          if seen[x][y]: continue
          seen[x][y] = 1
          todo.append((x,y))
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans < INF else -1)
  
if __name__ == "__main__":
  main()