AtCoder Beginner Contest 232 E

https://atcoder.jp/contests/abc232/tasks/abc232_e

まず縦の移動のみの場合の数を数えます。なぜなら、縦の移動回数をkとすれば、縦と横の移動が決まれば、それらの場合の数の積に $_KC_k$ を掛けたものになるからです。
1回の移動による場合の数は、 $x_1 = x_2$ のときは0です。 $x_1 \ne x_2$ のときは1です。どうやら、 $x_1 = x_2$ のときと $x_1 \ne x_2$ のときは別で考えなければならないようです。
そこで、k回移動で $x_1 = x_2$ のときの場合の数を $a_k$ 、 $x_1 \ne x_2$ のときの場合の数を $b_k$ と書くことにします。そうすると、
$a_1 = 0, b_1 = 1$
です。また、
$a_0 = 1, b_0 = 0$
です。漸化式を考えましょう。 $a_k (k \ge 1)$ を考えると、 $x_1 = x_2$ の状態から $x_1 = x_2$ の状態に遷移できないので、 $x_1 \ne x_2$ だけ考えます。H-1通りの $x_1 \ne x_2$ から遷移できるので、
$a_k = (H-1)b_{k-1}$
となります。 $x_1 \ne x_2$ の場合は、
$b_k = a_{k-1} + (H-2)b_{k-1}$
aの項を消すと、
$b_{k+1} = (H-2)b_k + (H-1)b_{k-1}$
$b_{k+1}+b_k = (H-1)(b_k+b_{k-1}) = (H-1)^k(b_1 + b_0) = (H-1)^k$
$b_{k+1}-(H-1)b_k = -(b_k-(H-1)b_{k-1}) = (-1)^k(b_1-(H-1)b_0) = (-1)^k$
$b_k = \frac{1}{H}( (H-1)^k - (-1)^k)$
$a_k = \frac{1}{H}( (H-1)^k + (-1)^k(H-1))$
となります。 $(-1)^k$ の係数が違うだけなので、縦の場合の数を $\frac{1}{H}( (H-1)^k ＋ p(-1)^k)$ 、横の場合の数を $\frac{1}{W}( (W-1)^k + q(-1)^k)$ と表すと、求める場合の数は、
$\displaystyle \frac{1}{HW}\sum_{k=0}^K{_KC_k( (H-1)^k ＋ p(-1)^k)( (W-1)^{K-k} + q(-1)^{K-k})}$
$\displaystyle = \frac{1}{HW}\sum_{k=0}^K{_KC_k( (H-1)^k(W-1)^{K-k} + p(-1)^k(W-1)^{K-k} + q(H-1)^k(-1)^{K-k} + pq(-1)^k(-1)^{K-k})}$
$= \displaystyle \frac{1}{HW}( (H+W-2)^K + p(W-2)^K + q(H-2)^K + pq(-2)^K)$
となります。

# coding: utf-8
# Rook Path

from itertools import *
import sys

sys.setrecursionlimit(2*10**5)


#################### library ####################

def read_tuple():
    return tuple(map(int, raw_input().split()))

# ax = by + c
def linear_diophantine(a, b, c):
    def f(a, b, c):
        if a == 1:
            return (b + c, 1)
        elif a == -1:
            return (-b - c, 1)
        
        d = b / a
        r = b % a
        t = f(r, a, -c)
        return (t[1] + d * t[0], t[0])
    
    return f(a, b, c)

def inverse(n, p):
    x, y = linear_diophantine(n, p, 1)
    return x


#################### process ####################

def read_input():
    H, W, K = read_tuple()
    x1, y1, x2, y2 = read_tuple()
    return (H, W, K, x1, y1, x2, y2)

def F(H, W, K, x1, y1, x2, y2):
    p = H - 1 if x1 == x2 else -1
    q = W - 1 if y1 == y2 else -1
    return (pow(H+W-2, K, D) + q * pow(H-2, K, D) +
            p * pow(W-2, K, D) + p * q * pow(-2, K, D)) * inverse(H*W, D) % D


#################### main ####################

D = 998244353
H, W, K, x1, y1, x2, y2 = read_input()
print F(H, W, K, x1, y1, x2, y2)