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

import sys
sys.setrecursionlimit(10**7)
MOD = 10**9+7

n = int(input())
g = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)

lim = 10**6 * 2
fact = [1, 1] + [0] * (lim-1)
fact_inv = [1, 1] + [0] * (lim-1)
inv = [0, 1] + [0] * (lim-1)
for i in range(2, lim+1):
    fact[i] = fact[i-1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD//i) % MOD
    fact_inv[i] = fact_inv[i-1] * inv[i] % MOD
def comb(n, m):
    if n < m or n < 0 or m < 0: return 0
    return fact[n] * (fact_inv[m] * fact_inv[n-m] % MOD) % MOD

dp = [1] * n
size = [0] * n

def dfs(v, pv):
    for nv in g[v]:
        if nv == pv: continue
        dfs(nv, v)
        ns = size[nv]+1
        size[v] += ns
        dp[v] *= dp[nv] * comb(size[v], ns) % MOD
        dp[v] %= MOD

def dfs2(v, pv):
    for nv in g[v]:
        if nv == pv: continue
        d, sz = dp[v], size[v]
        d *= inv[dp[nv]] * inv[comb(sz, size[nv]+1)] % MOD
        d %= MOD
        sz -= size[nv]+1

        size[nv] += sz+1
        dp[nv] *= d * comb(size[nv], sz+1) % MOD
        dp[nv] %= MOD
        dfs2(nv, v)

dfs(0, -1)
dfs2(0, -1)
print(*dp, sep="\n")


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = lambda: sys.stdin.readline().rstrip()
MOD = 10**9+7

n = int(input())
g = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)

lim = 10**5*2
fact = [1, 1] + [0] * (lim-1)
fact_inv = [1, 1] + [0] * (lim-1)
inv = [0, 1] + [0] * (lim-1)
for i in range(2, lim+1):
    fact[i] = fact[i-1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD//i) % MOD
    fact_inv[i] = fact_inv[i-1] * inv[i] % MOD
def comb(n, m):
    if n < m or n < 0 or m < 0: return 0
    return fact[n] * (fact_inv[m] * fact_inv[n-m] % MOD) % MOD
def icomb(n, m):
    if n < m or n < 0 or m < 0: return 0
    return fact_inv[n] * (fact[m] * fact[n-m] % MOD) % MOD

dp = [1] * n
size = [0] * n

def dfs(v, pv):
    for nv in g[v]:
        if nv == pv: continue
        dfs(nv, v)
        ns = size[nv]+1
        size[v] += ns
        dp[v] *= dp[nv] * comb(size[v], ns) % MOD
        dp[v] %= MOD

def dfs2(v, pv):
    for nv in g[v]:
        if nv == pv: continue
        d, sz = dp[v], size[v]
        d *= pow(dp[nv], MOD-2, MOD) * icomb(sz, size[nv]+1) % MOD
        d %= MOD
        sz -= size[nv]+1

        size[nv] += sz+1
        dp[nv] *= d * comb(size[nv], sz+1) % MOD
        dp[nv] %= MOD
        dfs2(nv, v)

dfs(0, -1)
dfs2(0, -1)
print(*dp, sep="\n")
### BUGGY CODE ###

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

ans = 0
for i in set(a):
  c = a.count(i)
  if c >= i:
    ans += c - i
  else:
    ans += c
print(ans)

### FIXED CODE ###

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

ans = 0
for i in set(a):
  if i <= n:
    c = a.count(i)
    if c >= i:
      ans += i
print(n - ans)
### BUGGY CODE ###

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

for k in range(K):
    for i in range(N):
        if A[i] != N:
            break
    else:
        break

    B = [0] * N
    for i in range(N):
        d = A[i]
        left = max(0, i - d)
        right = min(N-1, i + d)
        for index in range(left, right+1):
            B[index] += 1
    A = B
print(" ".join(map(str, A)))


### FIXED CODE ###

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

for k in range(K):
    for i in range(N):
        if A[i] != N:
            break
    else:
        break

    B = [0] * N
    for i in range(N):
        d = A[i]
        left = max(0, i - d)
        right = min(N-1, i + d)
        B[left] += 1
        if right + 1 < N:
            B[right+1] -= 1
    for i in range(1, N):
        B[i] += B[i-1]
    A = B
print(" ".join(map(str, A)))
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = {}
for i in range(N):
    routes[i] = []
for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = np.array([[mod,mod,mod] for i in range(N)])

# print(routes)
# def skip(now,move_cnt):
#     flag = True
#     if used[now] != mod:
#         if used[now] % 3 == 0 and move_cnt > used[now]:
#             flag = False
#     if used[now] > move_cnt:
#         if used[now] % 3 == 0 and move_cnt % 3 != 0:
#             pass
#         else:
#             used[now] = move_cnt
#     if flag:
#         for route in routes[now]:
#             skip(route,move_cnt+1)
# def move2next(now,move_cnt):
#     state = move_cnt % 3
#     if used[now, state] <= move_cnt:
#         flag = False # この条件だと前より遅いので探索ストップ
#     else:
#         used[now, state] = move_cnt
#         for route in routes[now]:
#             move2next(route, move_cnt+1)


q = queue.Queue()
q.put((S,0))
# Deep First Serch
def move2next(q):
    while q.qsize() > 0:
        now,cost = q.get()
        state = cost % 3
        if used[now, state] <= cost:
            pass
        else:
            used[now, state] = cost
            for route in routes[now]:
                q.put((route,cost+1))



move2next(q)
# print(used)
try:
    ans = used[T, 0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]

for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = [[mod,mod,mod] for i in range(N)]

from collections import deque

# q = queue.Queue()
q = deque()
q.append((S,0))
# Deep First Serch
while q:
    now, cost = q.popleft()
    for route in routes[now]:
        n_state = (cost + 1) % 3
        if used[route][n_state] == mod:
            used[route][n_state] = cost + 1
            q.append((route,cost+1))


# print(used)
try:
    ans = used[T][0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))
### BUGGY CODE ###

n = int(input())
s = input()
ans = s.count("R") * s.count("G") * s.count("B")

for i in range(n):
    for j in range(i+1,n):
        if s[i] != s[j]:
            k = j + (j - i)
            if k < n:
                if s[i] != s[j] != s[k] != s[i]:
                    # print(i, j, k)
                    ans -= 1

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = s.count("R") * s.count("G") * s.count("B")

for i in range(n):
    for j in range(i+1,n):
        if s[i] != s[j]:
            k = j + (j - i)
            if k >= n or j >= n:
                break
            if s[i] != s[j] != s[k] != s[i]:
                # print(i, j, k)
                ans -= 1

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

'''
n = int(input())
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [int(input()) for i in range n]
p = [list(map(int, input().split()))]

a = input()
a, b = input().split()
a = [input() for i in range n]
'''
n, a, b = map(int, input().split())

from math import factorial
import math


def nCr(n,r):
    return factorial(n) / factorial(r) / factorial(n - r)
mod = 10**9 + 7
sum = 2**(n%mod) - 1
sum -= (nCr(n,a) + nCr(n,b))

print(math.floor(sum%(10**9+7)))


### FIXED CODE ###

def solve():

    n, a, b = map(int, input().split())
    mod = 10**9 + 7

    # 繰り返し二乗法
    def modPow(a, n, mod):
        if n == 1:
            return a
        elif n%2 == 1:
            return a * modPow(a, n-1, mod) % mod
        else:
            t = modPow(a, n/2, mod)
            return (t * t) % mod

    def combination(n, a, mod):
        x = 1
        y = 1
        for i in range(a):
            x = x * (n-i)%mod
            y = y * (a-i)%mod

            #x *= (n-i)
            #x %=mod
            #y *= (a-i)
            #y %=mod
        return x * pow(y, mod-2, mod)%mod

    #全ての選び方
    sigma_nCi = pow(2, n, mod)
    # nCa, nCb
    nCa = combination(n, a, mod)
    nCb = combination(n, b, mod)

    ans = sigma_nCi - 1 - nCa - nCb

    #print(Sigma_nCi, nCa, nCb)
    print(ans%mod)

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

import math

s = list(input())
i = int(input())

isR = False
for _ in range(i):
    q = input().split(" ")

    if q[0] == "1":
        isR = not isR
    else:
        if isR:
            if q[1] == "1":
                s.append(q[2])
            else:
                s.insert(0, q[2])
        else:
            if q[1] == "1":
                s.insert(0, q[2])
            else:
                s.append(q[2])

if isR:
    print("".join(s[::-1]))
else:
    print("".join(s))

### FIXED CODE ###

import math

s = input()
i = int(input())

isR = False
head = []
tail = []

for _ in range(i):
    q = input().split(" ")

    if q[0] == "1":
        isR = not isR
    else:
        if isR:
            if q[1] == "1":
                tail.append(q[2])
            else:
                head.append(q[2])
        else:
            if q[1] == "1":
                head.append(q[2])
            else:
                tail.append(q[2])

ans = "".join(head[::-1]) + s + "".join(tail)

if isR:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

def bfs(S,H,W):
    stk = [(0,0)]
    cnt = 0
    seen = set()
    while True:
        nxt = []
        while stk:
            h,w = stk.pop()
            if(not (0<=h<H and 0<=w<W) or S[h][w]=='#' or (h,w) in seen):
                continue
            elif(h==H-1 and w==W-1):
                break
            seen.add((h,w))
            li=[(1,0),(-1,0),(0,-1),(0,1)]
            for x,y in li:
                nxt.append((h+y,w+x))
        else:
            stk = nxt
            cnt += 1
            continue
        break
    return cnt

H,W = [int(x) for x in input().split()]
S = [list(input()) for _ in range(H)]
wht = 0
for s in S:
    wht += s.count('.')
print(wht-(bfs(S,H,W)+1))


### FIXED CODE ###

def bfs(S,H,W):
    stk = [(0,0)]
    cnt = 0
    seen = set()
    while True:
        nxt = []
        while stk:
            h,w = stk.pop()
            if(not (0<=h<H and 0<=w<W) or S[h][w]=='#' or (h,w) in seen):
                continue
            elif(h==H-1 and w==W-1):
                break
            seen.add((h,w))
            li=[(1,0),(-1,0),(0,-1),(0,1)]
            for x,y in li:
                nxt.append((h+y,w+x))
        else:
            stk = nxt
            cnt += 1
            if(cnt>H*W+5):return -1
            continue
        break
    return cnt

H,W = [int(x) for x in input().split()]
S = [list(input()) for _ in range(H)]
wht = 0
for s in S:
    wht += s.count('.')
rt = bfs(S,H,W)
if(rt>=0):
    print(wht-(rt+1))
else:
    print(rt)
### 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

h,w,a,b = map(int,input().split())
res = 0
kai = min(w-b,h-a)
mod = 10**9+7

cmb1 = cmb(h-a-1+b,b) 
cmb2 = cmb(a+w-b-1,a) 
combi = cmb1 * cmb2 
res = combi

for i in range(1,kai):
    combi = (combi *(h-a-i)*(w-b-i))//((b+i)*(a+i))
    res += combi
    res %= mod

print(int(res))

### FIXED CODE ###

h, w, a, b = map(int, input().split())
res = 0
kai = min(w - b, h - a)
mod = 10 ** 9 + 7

kaijo = [0] * (h + w + 1)
kaijo[0] = 1
for i in range(1, h + w + 1):
    kaijo[i] = (kaijo[i - 1] * i) % mod
gyaku = [0] * (h + w + 1)
gyaku[h + w] = pow(kaijo[h + w], mod - 2, mod)
for i in range(h + w, 0, -1):
    gyaku[i - 1] = (gyaku[i] * i) % mod


def conb(x, k):
    return (kaijo[x] * gyaku[k] * gyaku[x - k]) % mod


conb1 = conb(h - a - 1 + b, b)
conb2 = conb(a + w - b - 1, a)
combi = conb1 * conb2
res = combi

for i in range(1, kai):
    res += conb(h - a - 1 + b, b + i) * conb(a + w - b - 1, a + i)

res %= mod
print(int(res))
### BUGGY CODE ###

def solve():
    S = input()
    T = input()
    len_t = len(T)
    len_s = len(S)
    dp = [[0] * (len_t+1) for _ in range(len_s+1)]
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            dp[i+1][j+1] = max(dp[i][j]+1 * (s == t),
                               dp[i][j+1],
                               dp[i+1][j])
    res = ''
    while len_t > 0 and len_s > 0:
        current = dp[len_s][len_t]
        if current == dp[len_s-1][len_t]:
            len_s -= 1
        elif current == dp[len_s][len_t-1]:
            len_t -= 1
        else:
            res = S[len_s-1] + res
            len_s -= 1
            len_t -= 1
    return res


if __name__ == "__main__":
    answer = solve()
    print(answer)


### FIXED CODE ###

def solve():
    S = input()
    T = input()
    len_t = len(T)
    len_s = len(S)
    dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
    for i, s in enumerate(S):
        pre_dp_i = dp[i]
        dp_i = dp[i+1]
        for j, t in enumerate(T):
            tmp_dp = max((pre_dp_i[j] + 1) * (s == t),
                         pre_dp_i[j+1],
                         dp_i[j])
            dp_i[j+1] = tmp_dp
    res = ''
    while len_t > 0 and len_s > 0:
        current = dp[len_s][len_t]
        if current == dp[len_s - 1][len_t]:
            len_s -= 1
        elif current == dp[len_s][len_t - 1]:
            len_t -= 1
        else:
            res = S[len_s - 1] + res
            len_s -= 1
            len_t -= 1
    return res


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

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ret = 0
    sum_list = [None] * n + [0]
    for i in range(n):
        sum_list[i] = sum(a[i:])
    for i in range(n):
        ret += a[i] * sum_list[i+1]
        ret %= 1000000007
    print(ret)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ret = 0
    sum_list = [None] * n + [0]
    for i in range(n-1, -1, -1):
        sum_list[i] = sum_list[i+1] + a[i]
    for i in range(n):
        ret += a[i] * sum_list[i+1]
        ret %= 1000000007
    print(ret)

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

a = set()
for _ in range(int(input())):
    a ^= {int(input())}
print(len(a))

### FIXED CODE ###

a = set()
for _ in range(int(input())):
    a ^= {input()}
print(len(a))
### BUGGY CODE ###

N, M = map(int, input().split())
L = list(map(int, input().split()))
 
if N == 1:
	if L[0]%M == 0:
		print(1)
		exit()
	else:
		print(0)
		exit()

for i in range (0, N):
	L[i] = L[i]%M

count = 0
 
for i in range (1, N):
	L[i]+= L[i-1]
    
for i in range (0, N):
	L[i] = L[i]%M

L = sorted(L)
 
alreadythere = []
 
for i in range (0, N):
	if alreadythere.count(L[i])>0 or L[i] == 0:
		continue
	else:
		alreadythere.append(L[i])
		V = L[i]
		D = L.count(L[i])
		count+= int(D*(D-1)/2)

V = L.count(0)
count+= V+int(V*(V-1)/2)
 
print(count)

### FIXED CODE ###

N, M = map(int, input().split())
L = list(map(int, input().split()))

if N == 1:
	if L[0]%M == 0:
		print(1)
		exit()
	else:
		print(0)
		exit()

for i in range (0, N):
	L[i] = L[i]%M

count = 0

for i in range (1, N):
	L[i]= (L[i-1]+L[i])%M

L = sorted(L)

alreadythere = []
import collections

cnt = collections.Counter()
for number in L:
	cnt[number] += 1

L = set(L)

for i in L:
	if i == 0:
		K = cnt[i]
		count+=(int(K*(K-1)/2)+K)
	else:
		K = cnt[i]
		count+=int(K*(K-1)/2)

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

from functools import reduce
import fractions
import sys
sys.setrecursionlimit(20000)

def lcm_base(a, b):
    return a * b / fractions.gcd(a, b)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
A = list(map(int, input().split()))
B = [0 for _ in range(N)]
mod = 10**9+7

ll = lcm_list(A)
ans = 0
for i in range(N):
    B[i] = (ll//A[i])%mod
    ans += B[i]
print(int(ans%mod))


### FIXED CODE ###

from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    #ans%=mod
print(ans%mod)
### BUGGY CODE ###

N=int(input())
word=[]
word_lst=[]
for i in range(N):
  s=input()
  word.append(s)
  word_lst.append(list(word[i]))
  word_lst[i].sort()

count=0
for i in range(N):
  for j in range(N):
    if word_lst[i]==word_lst[j]:
      count=count+1

total=int((count-N)/2)
  
  
print(total)  


### FIXED CODE ###

import collections

n=int(input())
s=[]
set={}
for i in range(n):
    s.append(input())
for i in range(n):
    temp=list(s[i])
    temp.sort()
    s[i]=''.join(temp)
count=0
ans=collections.Counter(s)
countlist=ans.most_common()
for i in range(len(countlist)):
    if countlist[i][1]<=1:
        break
    else:
        temp=countlist[i][1]-1
        count+=(temp+1)*temp//2

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

INF = float('inf')

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [INF for _ in range(N)]  # dp[足場index - 1] = 最小コスト
dp[0] = 0

for j in range(1, N):
    for i in range(max(0, j - K), j - 1 + 1):
        dp[j] = min(dp[j], dp[i] + abs(h[j] - h[i]))

print(dp[N - 1])


### FIXED CODE ###

INF = 10 ** 10

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [INF for _ in range(N)]
dp[0] = 0
# 0-indexed

for i in range(1, N):
    for k in range(1, K + 1):
        if i - k >= 0:
            dp[i] = min(dp[i], dp[i - k] + abs(h[i] - h[i - k]))

print(dp[N - 1])
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))
def rec(i, m):
    if m == 0:
        return True
    if i >= n:
        return False
    res = rec(i + 1, m) | rec(i + 1, m - A[i])
    return res
for m in M:
    if rec(0, m):
        print('yes')
    else:
        print('no')


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))
bits = 1
for a in A:
    bits |= bits << a
for m in M:
    print('yes' if (bits >> m) & 1 else 'no')
### BUGGY CODE ###

# 整数の入力
import numpy as np
N = int(input())
S = input()


def check_condition(S):
    N = len(S)
    ind = np.where(S=="R")[0]
    if len(ind) == 0 or len(ind) == N:
        return True
    
    if np.max(ind) == len(ind) - 1:
        return True
    
    return False

def action(S):
    W_index = np.where(S=="W")[0][0]
    R_index = np.where(S=="R")[0][-1]
    S[W_index] = "R"
    S[R_index] = "W"
    return S

def alter(S, M):
    if check_condition(S):
        return M
    
    S = action(S)
    
    return alter(S, M+1)

S = np.array(list(S))
print(alter(S,0))

### FIXED CODE ###

# 整数の入力
import numpy as np

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


def check_condition(S):
    N = len(S)
    ind = np.where(S=="R")[0]
    if len(ind) == 0 or len(ind) == N:
        return True
    
    if np.max(ind) == len(ind) - 1:
        return True
    
    return False

def alter(S):
    if check_condition(S):
        return 0
    ind = np.where(S=="R")[0]
    num_r = len(ind)
    num_offset = np.sum(ind > num_r - 1)
    return num_offset

S = np.array(list(S))
print(alter(S))
### BUGGY CODE ###

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

b = []
for i in range(N):
    b.append(A[i])
    b = b[::-1]
print(" ".join(b))


### FIXED CODE ###

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

b = A[::2][::-1] + A[1::2]
if N % 2 == 0:
    b = b[::-1]
print(" ".join(b))
### BUGGY CODE ###

h,n=map(int,input().split())
magic=[list(map(int,input().split())) for _ in range(n)]
dp=[10**9]*(h+10**5)
#dp[i]:敵の体力をi減らすのに必要な魔力の最小値
dp[0]=0
for i in range(h):
    for damage,cost in magic:
        dp[i+damage]=min(dp[i+damage],dp[i]+cost)
ans=10**9
for i in range(10**5):
    ans=min(ans,dp[i+h])
print(ans)

### FIXED CODE ###

h,n=map(int,input().split())
magic=[list(map(int,input().split())) for _ in range(n)]
dp=[10**9]*(h+10**5)
#dp[i]:敵の体力をi減らすのに必要な魔力の最小値
dp[0]=0
for i in range(h):
    for damage,cost in magic:
        dp[i+damage]=min(dp[i+damage],dp[i]+cost)
ans=10**9
for i in range(10**5):
    ans=min(ans,dp[i+h])
print(ans)
### BUGGY CODE ###

from collections import deque
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

inf = 10**9
dp = [[inf for j in range(w)] for k in range(h)]
dp[x1-1][y1-1] = 0
q = deque([(x1-1, y1-1)])

while q:
    x, y = q.popleft()
    if (x, y) == (x2-1, y2-1):
        break
    c = dp[x][y]
    for i in range(x+1, min(x+k+1, h)):
        if g[i][y] == "@":
            break
        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
            q.append((i, y))
        else:
            break


    for i in range(x-1, max(x-k-1, -1), -1):
        if g[i][y] == "@":
            break
        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
            q.append((i, y))
        else:
            break

    for j in range(y+1, min(y+k+1, w)):
        if g[x][j] == "@":
            break
        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
            q.append((x, j))
        else:
            break


    for j in range(y-1, max(y-k-1, -1), -1):
        if g[x][j] == "@":
            break
        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
            q.append((x, j))
        else:
            break

if dp[x2-1][y2-1] == inf:
    print(-1)
else:
    print(dp[x2-1][y2-1])


### FIXED CODE ###

from collections import deque
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

inf = 10**9
dp = [[inf for j in range(w)] for k in range(h)]
dp[x1-1][y1-1] = 0
q = deque([(x1-1, y1-1)])

while q:
    x, y = q.popleft()
    if (x, y) == (x2-1, y2-1):
        break
    c = dp[x][y]
    for i in range(x+1, min(x+k+1, h)):
        if g[i][y] == "@":
            break

        if dp[i][y] == inf:
           q.append((i, y))

        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
        else:
            break


    for i in range(x-1, max(x-k-1, -1), -1):
        if g[i][y] == "@":
            break

        if dp[i][y] == inf:
           q.append((i, y))

        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
        else:
            break

    for j in range(y+1, min(y+k+1, w)):
        if g[x][j] == "@":
            break

        if dp[x][j] == inf:
            q.append((x, j))

        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
        else:
            break


    for j in range(y-1, max(y-k-1, -1), -1):
        if g[x][j] == "@":
            break

        if dp[x][j] == inf:
            q.append((x, j))

        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
        else:
            break

if dp[x2-1][y2-1] == inf:
    print(-1)
else:
    print(dp[x2-1][y2-1])