CodeEff/ECCO huggingface dataset:
# Original solution
from math import ceil

# 入力
N = int(eval(input()))
A = [int(eval(input())) for i in range(N)]

MOD = 998244353


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )


S = sum(A)
# 赤色の整数の和がiとなるような塗り方の個数
dp = [ModInt(0) for _ in range(S + 1)]
dp[0] = ModInt(1)
# 赤色の整数の和がi, 他の整数がすべて青色となるような塗り方の個数
dp2 = [ModInt(0) for _ in range(S // 2 + 1)]
dp2[0] = ModInt(1)

# 動的計画法により、dp, dp2を求める
for a in A:
    for i in range(S, a - 1, -1):
        dp[i] = dp[i] * 2 + dp[i - a]
    for i in range(a - 1, -1, -1):
        dp[i] = dp[i] * 2
    for i in range(S // 2, a - 1, -1):
        dp2[i] = dp2[i] + dp2[i - a]

# 全ての塗り方の個数から、条件を満たさない塗り方の個数を差し引いて解を求める
ans = 3**N - 3 * sum(dp[ceil(S / 2):]) + (
    3 * dp2[S // 2] if S % 2 == 0 else
    0
)

# 出力
print(ans)


# Optimized solution
from math import ceil

# 入力
N = int(eval(input()))
A = [int(eval(input())) for i in range(N)]

MOD = 998244353


S = sum(A)
# 赤色の整数の和がiとなるような塗り方の個数
dp = [0 for _ in range(S + 1)]
dp[0] = 1
# 赤色の整数の和がi, 他の整数がすべて青色となるような塗り方の個数
dp2 = [0 for _ in range(S // 2 + 1)]
dp2[0] = 1

# 動的計画法により、dp, dp2を求める
for a in A:
    for i in range(S, a - 1, -1):
        dp[i] = (2 * dp[i] + dp[i - a]) % MOD
    for i in range(a - 1, -1, -1):
        dp[i] = (2 * dp[i]) % MOD
    for i in range(S // 2, a - 1, -1):
        dp2[i] = (dp2[i] + dp2[i - a]) % MOD

# 全ての塗り方の個数から、条件を満たさない塗り方の個数を差し引いて解を求める
ans = (3**N - 3 * sum(dp[ceil(S / 2):]) + (
    3 * dp2[S // 2] if S % 2 == 0 else
    0
)) % MOD

# 出力
print(ans)
# Original solution
import sys
input = sys.stdin.readline

N=int(eval(input()))
A=[int(eval(input())) for i in range(N)]
SUM=sum(A)
MAX=(SUM-1)//2

mod=998244353
from collections import Counter

DPLIST=[[0]*301 for i in range(MAX+2)]
DPLIST[0][0]=1
ANS=0

for a in A:
    for i in range(299,-1,-1):
        for j in range(MAX+1,-1,-1):
            DPLIST[min(j+a,MAX+1)][i+1]+=DPLIST[j][i]

ANS=(pow(3,N,mod)-3*pow(2,N,mod))%mod
MINUS=0

for i in range(N-1):
    MINUS+=3*(pow(2,(N-i),mod)-2)*DPLIST[MAX+1][i]

print(((ANS-MINUS+3)%mod))

# Optimized solution
import sys
input = sys.stdin.readline

N=int(eval(input()))
A=[int(eval(input())) for i in range(N)]
SUM=sum(A)
MAX=(SUM-1)//2

mod=998244353

DPLIST=[0]*(MAX+2)
DPLIST[0]=1

for a in A:
    for i in range(MAX+1,-1,-1):
        if i==MAX+1:
            DPLIST[i]=DPLIST[i]*3%mod
        else:
            DPLIST[min(i+a,MAX+1)]=(DPLIST[min(i+a,MAX+1)]+DPLIST[i])%mod
            DPLIST[i]=DPLIST[i]*2%mod

if SUM%2==1:
    print(((sum(DPLIST)-DPLIST[-1]*3)%mod))
    sys.exit()

MAX=SUM//2
       
DPLIST2=[0]*(MAX+2)
DPLIST2[0]=1

for a in A:
    for i in range(MAX+1,-1,-1):
        DPLIST2[min(i+a,MAX+1)]=(DPLIST2[min(i+a,MAX+1)]+DPLIST2[i])%mod

        
print(((sum(DPLIST)-DPLIST[-1]*3+DPLIST2[-2]*3)%mod))
# Original solution
N = int(eval(input()))
A = [int(eval(input())) for i in range(N)]
MOD = 998244353

S = sum(A)

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

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

for i in range(N):
    a = A[i]
    x = 0
    while x <= S:
        if x + a <= S:
            dp[i+1][x+a] += dp[i][x]
            dp2[i+1][x+a] += dp2[i][x]
        dp[i+1][x] += dp[i][x] * 2
        dp2[i+1][x] += dp2[i][x]
        x += 1



if S % 2 == 0:
    ans = 3 ** N - sum(dp[N][S//2:]) * 3
    ans += 3 * dp2[N][S//2]
else:
    ans = 3 ** N - sum(dp[N][S//2 + 1:]) * 3

print((ans % MOD))

# Optimized solution
N = int(eval(input()))
A = [int(eval(input())) for i in range(N)]
MOD = 998244353

S = sum(A)

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

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

for i in range(N):
    a = A[i]
    x = 0
    while x <= S:
        if x + a <= S:
            dp[i+1][x+a] += dp[i][x] % MOD
            dp2[i+1][x+a] += dp2[i][x] % MOD
        dp[i+1][x] += dp[i][x] * 2 % MOD
        dp2[i+1][x] += dp2[i][x] % MOD
        x += 1


if S % 2 == 0:
    ans = 3 ** N - sum(dp[N][S//2:]) * 3
    ans += 3 * dp2[N][S//2]
else:
    ans = 3 ** N - sum(dp[N][S//2 + 1:]) * 3

print((ans % MOD))
# Original solution
MOD = 998244353
def pow(n,k,m):#n^k mod m
    ans = 1
    while k>0:
        if(k & 1):ans = (ans*n) % m
        n = (n*n)%m
        k >>= 1
    return ans

n = int(eval(input()))
a =[int(eval(input())) for i in range(n)]
s = sum(a)
dp1 = [0 for i in range(s+1)] #dp1[x]:Bの和=xとなるような塗り方の総数

dp1[0] = 1

for i in range(n):
    dpp1 = [0 for i in range(s+1)]
    for j in range(s+1):
        if j+a[i] <= s:dpp1[j+a[i]] = (dp1[j]+dpp1[j+a[i]]) % MOD
        dpp1[j] = (dp1[j]*2 + dpp1[j]) % MOD
    dp1 = dpp1[:]

if s % 2 == 1:
    ans1 = sum(dp1[(s//2) + 1:]) % MOD
    print(((pow(3,n,MOD)-ans1*3) % MOD))
    exit()

ans1 = sum(dp1[(s//2):]) % MOD

dp2 = [0 for i in range(s+1)]

dp2[0] = 1

for i in range(n):
    dpp2 = [0 for i in range(s+1)]
    for j in range(s+1):
        if j+a[i] <= s:dpp2[j+a[i]] = (dp2[j]+dpp2[j+a[i]]) % MOD
        dpp2[j] = (dp2[j] + dpp2[j]) % MOD
    dp2 = dpp2[:]

print(((pow(3,n,MOD)-(ans1*3 - dp2[s//2]*3)) % MOD))

# Optimized solution
MOD = 998244353
def pow(n,k,m):#n^k mod m
    ans = 1
    while k>0:
        if(k & 1):ans = (ans*n) % m
        n = (n*n)%m
        k >>= 1
    return ans

n = int(eval(input()))
a =[int(eval(input())) for i in range(n)]
s = sum(a)
dp1 = [0 for i in range(s+1)] #dp1[x]:Bの和=xとなるような塗り方の総数

dp1[0] = 1

for i in  a:
    dpp1 = [0 for i in range(s+1)]
    for j in range(s+1):
        if j+i <= s:dpp1[j+i] = (dp1[j]+dpp1[j+i]) % MOD
        dpp1[j] = (dp1[j]*2 + dpp1[j]) % MOD
    dp1 = dpp1[:]

if s % 2 == 1:
    ans1 = sum(dp1[(s//2) + 1:]) % MOD
    print(((pow(3,n,MOD)-ans1*3) % MOD))
    exit()

ans1 = sum(dp1[(s//2):]) % MOD

dp2 = [0 for i in range(s+1)]

dp2[0] = 1

for i in a:
    dpp2 = [0 for i in range(s+1)]
    for j in range(s+1):
        if j+i <= s:dpp2[j+i] = (dp2[j]+dpp2[j+i]) % MOD
        dpp2[j] = (dp2[j] + dpp2[j]) % MOD
    dp2 = dpp2[:]

print(((pow(3,n,MOD)-(ans1*3 - dp2[s//2]*3)) % MOD))
# Original solution
M,z,s=998244353,1,0
N,*A=list(map(int,open(0)))
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for a in A:
 i=s;s+=a;z*=3
 while~i:d[i+a]+=d[i]%M;d[i]*=2;e[i+a]+=e[i]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
print(((z+~s%2*e[s//2]*3)%M))

# Optimized solution
M,z,s=998244353,1,0
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for _ in'_'*eval(input()):
 a=eval(input());s+=a;i=s;z*=3
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
print((z+~s%2*e[s//2]*3)%M)
# Original solution
M,z,s=998244353,1,0
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for _ in'_'*eval(input()):
 a=eval(input());s+=a;i=s;z*=3
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a];i-=1
i=s
while i*2>=s:z-=d[i]*3;i-=1
print((z+~s%2*e[s//2]*3)%M)

# Optimized solution
M,z,s=998244353,1,0
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for _ in'_'*eval(input()):
 a=eval(input());s+=a;i=s;z*=3
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z-=d[i]*3;i-=1
print((z+~s%2*e[s//2]*3)%M)
# Original solution
M,z,s=998244353,1,0
N,*A=open(0)
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for a in A:
 a=int(a);s+=a;i=s;z*=3
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
print(((z+~s%2*e[s//2]*3-3*sum(d[-~s//2:]))%M))

# Optimized solution
M,s=998244353,0
d=[1]+[0]*7**6
e=d[:]
n=eval(input())
for _ in'_'*n:
 a=eval(input());s+=a;i=s
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
print((3**n+~s%2*e[s//2]*3-3*sum(d[-~s//2:]))%M)
# Original solution
mod = 998244353
N = int(eval(input()))
A = [int(eval(input())) for i in range(N)]
A.sort()
S = sum(A)

PS = [0 for i in range(N+1)]
for i in range(N):
    PS[i+1] = PS[i] + A[i]

# D[i][r]: i個塗った時点でR=rとなる場合の数
D = [[0 for _ in range(PS[i]+1)] for i in range(N+1)]
D[0][0] = 1
# D2[i][r]: i個塗った時点でR=r, B=0となる場合の数
D2 = [[0 for _ in range(PS[i]+1)] for i in range(N+1)]
D2[0][0] = 1

for i in range(N):
    for j in range(PS[i]+1):
        if D[i][j] == 0:
            continue
        D[i+1][j] += D[i][j] * 2
        D[i+1][j+A[i]] += D[i][j]

for i in range(N):
    for j in range(PS[i]+1):
        if D2[i][j] == 0:
            continue
        D2[i+1][j] += D2[i][j]
        D2[i+1][j+A[i]] += D2[i][j]

border = (S + 1) // 2

result = 3 ** N
result -= 3 * sum(D[N][border:])
if border * 2 == S:
    result += 3 * D2[N][border]

print((result % mod))


# Optimized solution
mod = 998244353
N = int(eval(input()))
A = [int(eval(input())) for i in range(N)]
A.sort()
S = sum(A)

PS = [0 for i in range(N+1)]
for i in range(N):
    PS[i+1] = PS[i] + A[i]

# D[i][r]: i個塗った時点でR=rとなる場合の数
D = [[0 for _ in range(PS[i]+1)] for i in range(N+1)]
D[0][0] = 1
# D2[i][r]: i個塗った時点でR=r, B=0となる場合の数
D2 = [[0 for _ in range(PS[i]+1)] for i in range(N+1)]
D2[0][0] = 1

for i in range(N):
    for j in range(PS[i]+1):
        if D[i][j] == 0:
            continue
        D[i+1][j] = (D[i+1][j] + D[i][j] * 2) % mod
        D[i+1][j+A[i]] = (D[i+1][j+A[i]] + D[i][j]) % mod

for i in range(N):
    for j in range(PS[i]+1):
        if D2[i][j] == 0:
            continue
        D2[i+1][j] = (D2[i+1][j] + D2[i][j]) % mod
        D2[i+1][j+A[i]] = (D2[i+1][j+A[i]] + D2[i][j]) % mod

border = (S + 1) // 2

result = 3 ** N
result -= 3 * sum(D[N][border:])
if border * 2 == S:
    result += 3 * D2[N][border]

print((result % mod))
# Original solution
from collections import deque
import sys

def bfs(M, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    M[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return M[y][x]
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            for k in range(1, K + 1):
                new_x = x + dx * k
                new_y = y + dy * k

                if (0 <= new_y < H) and (0 <= new_x < W):
                    if m[new_y][new_x] == "@":
                        break
                    elif M[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        M[new_y][new_x] = M[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif M[new_y][new_x] < M[y][x] + 1:
                        break
                else:
                    break


H, W, K = list(map(int, input().split()))
# K = min(K, max(H, W))
x1, y1, x2, y2 = list(map(int, input().split()))
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))
    
M = [[-1] * W for i in range(H)]

bfs(M, x1, y1, x2, y2)

print((M[x2][y2]))


# Optimized solution
from collections import deque
import sys


def bfs(M, sy, sx):
    queue = deque([[xs, ys]])
    M[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        x1, y1 = queue.popleft()  # queueに入っていたものを消す。
        if [x1, y1] == [xg, yg]:  # もしゴールについていたならば、そのときの手数を出す。
            return M[x1][y1]
        
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            for k in range(1, K + 1):
                new_x = x1 + dx * k
                new_y = y1 + dy * k

                if (0 <= new_x < H) and (0 <= new_y < W):
                    if m[new_x][new_y] == "@":
                        break
                    elif M[new_x][new_y] == -1:  # まだ来たことない点だったという条件
                        M[new_x][new_y] = M[x1][y1] + 1
                        queue.append([new_x, new_y])  # 新しい点を足す。
                    elif M[new_x][new_y] < M[x1][y1] + 1:
                        break
                else:
                    break


H, W, K = list(map(int, input().split()))
# K = min(K, max(H, W))
xs, ys, xg, yg = list(map(int, input().split()))
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(M, xs, ys)

print((M[xg][yg]))
# Original solution
from collections import deque
import sys


def bfs(xs, ys):
    queue = deque([[xs, ys]])
    M[xs][ys] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        x1, y1 = queue.popleft()  # queueに入っていたものを消す。
        if [x1, y1] == [xg, yg]:  # もしゴールについていたならば、そのときの手数を出す。
            return M[x1][y1]

        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            for k in range(1, K + 1):
                new_x = x1 + dx * k
                new_y = y1 + dy * k

                if (0 <= new_x < H) and (0 <= new_y < W):
                    if m[new_x][new_y] == "@":
                        break
                    elif M[new_x][new_y] == -1:  # まだ来たことない点だったという条件
                        M[new_x][new_y] = M[x1][y1] + 1
                        queue.append([new_x, new_y])  # 新しい点を足す。
                    elif M[new_x][new_y] < M[x1][y1] + 1:
                        break
                else:
                    break


H, W, K = list(map(int, input().split()))
# K = min(K, max(H, W))
xs, ys, xg, yg = list(map(int, input().split()))
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys)

print((M[xg][yg]))


# Optimized solution
from collections import deque
import sys


def bfs(xs, ys, d):
    queue = deque()
    queue.append((xs, ys, d))
    M[xs][ys] = d
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        x1, y1, d = queue.popleft()  # queueに入っていたものを消す。
        if [x1, y1] == [xg, yg]:  # もしゴールについていたならば、そのときの手数を出す。
            return

        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == "@":
                        break
                    elif M[x2][y2] == -1:  # まだ来たことない点だったという条件
                        M[x2][y2] = d + 1
                        queue.append((x2, y2, d + 1))  # 新しい点を足す。
                    elif M[x2][y2] < d + 1:
                        break
                else:
                    break


H, W, K = list(map(int, input().split()))
# K = min(K, max(H, W))
xs, ys, xg, yg = list(map(int, input().split()))
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)

print((M[xg][yg]))
# Original solution
import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                # if m[x2][y2] == '@':
                #     break
                # if x2 < 0 or x2 >= H:
                #     break
                # if y2 < 0 or y2 >= W:
                #     break
                # if M[x2][y2] < d + 1:
                #     break
                # if M[x2][y2] == d + 1:
                #     continue

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        M[x2][y2] = d + 1
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] <= d:
                        break
                    elif M[x2][y2] == d + 1:
                        continue
                    else:
                        break
    print((-1))


H, W, K = list(map(int, sys.stdin.readline().strip().split()))
xs, ys, xg, yg = list(map(int, sys.stdin.readline().strip().split()))
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)


# Optimized solution
import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                # if m[x2][y2] == '@':
                #     break
                # if x2 < 0 or x2 >= H:
                #     break
                # if y2 < 0 or y2 >= W:
                #     break
                # if M[x2][y2] < d + 1:
                #     break
                # if M[x2][y2] == d + 1:
                #     continue

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        M[x2][y2] = d + 1
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] <= d:
                        break
                    elif M[x2][y2] == d + 1:
                        continue
                    else:
                        break
                else:
                    break
    print((-1))


H, W, K = list(map(int, sys.stdin.readline().strip().split()))
xs, ys, xg, yg = list(map(int, sys.stdin.readline().strip().split()))
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)
# Original solution
import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:  # 枠外
                    break
                if y2 < 0 or y2 >= W:  # 枠外
                    break
                if m[x2][y2] == '@':  # 蓮の葉
                    break
                if M[x2][y2] < d + 1:  # より良い経路を探索済み。
                    break
                if M[x2][y2] == d + 1:  # 同等の良さの経路を探索済み。　飛び越えて次のマスを探索する。
                    continue

                q.append((d + 1, x2, y2))
                M[x2][y2] = d + 1

    print((-1))


H, W, K = list(map(int, sys.stdin.readline().strip().split()))
xs, ys, xg, yg = list(map(int, sys.stdin.readline().strip().split()))
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)


# Optimized solution
import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()
        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:  # 枠外
                    break
                if y2 < 0 or y2 >= W:  # 枠外
                    break
                if m[x2][y2] == '@':  # 蓮の葉
                    break
                if M[x2][y2] < d + 1:  # より良い経路を探索済み。
                    break
                if M[x2][y2] == d + 1:  # 同等の良さの経路を探索済み。　飛び越えて次のマスを探索する。
                    continue

                q.append((d + 1, x2, y2))
                M[x2][y2] = d + 1

    print((-1))


H, W, K = list(map(int, sys.stdin.readline().strip().split()))
xs, ys, xg, yg = list(map(int, sys.stdin.readline().strip().split()))
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)
# Original solution
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from collections import deque
INF = float('inf')


def main():
    import sys
    read = sys.stdin.read
    readline = sys.stdin.readline
    readlines = sys.stdin.readlines
    from collections import deque

    H, W, K = list(map(int, readline().split()))
    x1, y1, x2, y2 = list(map(int, readline().split()))
    x1 -= 1;
    y1 -= 1;
    x2 -= 1;
    y2 -= 1
    C = read().split()

    dist = [[-1] * W for i in range(H)]
    dist[x1][y1] = 0
    d = deque([[x1, y1]])
    dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    while d:
        x, y = d.popleft()
        if (x, y) == (x2, y2):
            print((dist[x][y]))
            quit()
        for dx, dy in dxy:
            xx = x;
            yy = y
            for i in range(K):
                xx += dx;
                yy += dy
                if 0 <= xx < H and 0 <= yy < W and C[xx][yy] != '@':
                    if 0 <= dist[xx][yy] <= dist[x][y]:
                        break
                    if dist[xx][yy] == -1:
                        d.append([xx, yy])
                    dist[xx][yy] = dist[x][y] + 1
                else:
                    break

    print((-1))


if __name__ == '__main__':
    main()


# Optimized solution
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from collections import deque
INF = float('inf')


def main():
    H, W, K = list(map(int, readline().split()))
    x1, y1, x2, y2 = list(map(int, readline().split()))
    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1
    C = read().split()

    dist = [[-1] * W for i in range(H)]
    dist[x1][y1] = 0
    d = deque([[x1, y1]])
    dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    while d:
        x, y = d.popleft()
        if (x, y) == (x2, y2):
            print((dist[x][y]))
            quit()
        for dx, dy in dxy:
            xx = x
            yy = y
            for i in range(K):
                xx += dx;
                yy += dy
                if 0 <= xx < H and 0 <= yy < W and C[xx][yy] != '@':
                    if 0 <= dist[xx][yy] <= dist[x][y]:
                        break
                    if dist[xx][yy] == -1:
                        d.append([xx, yy])
                    dist[xx][yy] = dist[x][y] + 1
                else:
                    break

    print((-1))


if __name__ == '__main__':
    main()