\(k\) 回の操作後にルークが \((i, j)\) に置かれているようにする方法の総数を \(f_{k, i, j}\) とおきます。\(f_{K, x_2, y_2}\) が答えとなります。

\(i = x_1\) かつ \(j = y_1\) のとき \(f_{0, i, j} = 1, \) そうでないときは \(f_{0, i, j} = 0\) です。\(k > 0\) については、以下の関係が成り立ちます。

• \(f_{k, i, j} = \sum_{x \neq i} f_{k - 1, x, j} + \sum_{y \neq j} f_{k - 1, i, y}\)

この値の計算を愚直に行うと、\(\Theta (N^3 K)\) の時間計算量を要するため、\(f\) の特徴を利用して計算を高速化する必要があります。

実際に \(f_{k, i, j}\) を計算してみると、多くの値が等しくなっており、各 \(k\) ごとに \(f_{k, i, j}\) の値の種類は高々 \(4\) 通りであることに気づくでしょう。状態数を圧縮して計算するため、グリッド上のマスの集合を以下の \(4\) つに分けます。

• \(S_{0, 0} = \{ (x_2, y_2) \}\)
• \(S_{0, 1} = \{ (x_2, y) \, \vert \, y \neq y_2 \}\)
• \(S_{1, 0} = \{ (x, y_2) \, \vert \, x \neq x_2 \}\)
• \(S_{1, 1} = \{ (x, y) \, \vert \, x \neq x_2 \land y \neq y_2 \}\)

\(g_{k, a, b} = \sum_{(i, j) \in S_{a, b}} f(k, i, j)\) と定義します。すると、\(k > 0\) に対し以下の関係が成り立ちます。

• \(g_{k, 0, 0} = g_{k - 1, 0, 1} + g_{k - 1, 1, 0}\)
• \(g_{k, 0, 1} = (Y - 1) g_{k - 1, 0, 0} + (Y - 2) g_{k - 1, 0, 1} + g_{k - 1, 1, 1}\)
• \(g_{k, 1, 0} = (X - 1) g_{k - 1, 0, 0} + (X - 2) g_{k - 1, 1, 0} + g_{k - 1, 1, 1}\)
• \(g_{k, 1, 1} = (X - 1)g_{k - 1, 0, 1} + (Y - 1)g_{k - 1, 1, 0} + (X - 2 + Y - 2) g_{k - 1, 1, 1}\)

\(g_{K, 0, 0}\) が答えとなります。計算量は \(O(K)\) です。

実装例 (C++) :

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;

using Fp = modint998244353;

int main() {
    int h, w, k;
    cin >> h >> w >> k;
    array<array<Fp, 2>, 2> dp = {};
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    dp[x1 != x2][y1 != y2] = 1;
    array<Fp, 2> row = {1, h - 1}, col = {1, w - 1};
    while (k--) {
        array<array<Fp, 2>, 2> next = {};
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                for (int a = 0; a < 2; ++a) {
                    next[i][a] += dp[i][j] * (col[a] - (j == a));
                    next[a][j] += dp[i][j] * (row[a] - (i == a));
                }
            }
        }
        dp = move(next);
    }
    cout << dp[0][0].val() << '\n';
    return 0;
}

余談 : 行列累乗などを用いて \(O(\log K)\) で解くこともできます。