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$ 取模后的结果。

输入输出样例 #1

输入 #1

2 2 2
1 2 2 1

输出 #1

2

输入输出样例 #2

输入 #2

1000000000 1000000000 1000000
1000000000 1000000000 1000000000 1000000000

输出 #2

24922282

输入输出样例 #3

输入 #3

3 3 3
1 3 3 3

输出 #3

9

说明/提示

限制条件

• $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 翻译