AT_abc232_e.[ABC232E] Rook Path

有一个由 $H$ 行 $W$ 列组成的 $H \times W$ 的网格。第 $i$ 行第 $j$ 列的格子记作 $(i, j)$。

一开始，棋盘上的 $(x_1, y_1)$ 位置上放有一个“车”（rook），高桥君将进行 $K$ 次如下操作：

• 将车移动到与当前所在格子同行或同列的另一个格子（不能停在原地）。

请问经过 $K$ 次操作后，车恰好停在 $(x_2, y_2)$ 这个格子的方案数有多少种？答案可能非常大，请输出对 $998244353$ 取模的结果。

输入从标准输入中给出，格式如下：

$H$ $W$ $K$ $x_1$ $y_1$ $x_2$ $y_2$

输出经过 $K$ 次操作后，车恰好停在 $(x_2, y_2)$ 这个格子的方案数，对 $998244353$ 取模后的结果。

限制条件

• $2 \leq H, W \leq 10^9$
• $1 \leq K \leq 10^6$
• $1 \leq x_1, x_2 \leq H$
• $1 \leq y_1, y_2 \leq W$

样例解释 1

有以下 $2$ 种方案：

• 第 $1$ 次操作将车从 $(1, 2)$ 移动到 $(1, 1)$，第 $2$ 次操作将车从 $(1, 1)$ 移动到 $(2, 1)$。
• 第 $1$ 次操作将车从 $(1, 2)$ 移动到 $(2, 2)$，第 $2$ 次操作将车从 $(2, 2)$ 移动到 $(2, 1)$。

样例解释 2

请注意，答案需要对 $998244353$ 取模。

由 ChatGPT 4.1 翻译