Score : $500$ points

问题陈述

存在一个 $H \times W$ 的棋盘格，包含 $H$ 行（从上至下编号）和 $W$ 列（从左至右编号）。令 $(i, j)$ 表示第 $i$ 行从上数起、第 $j$ 列从左数起的方格。

棋盘上有一个初始位于 $(x_1, y_1)$ 的车（rook）。Takahashi 将执行以下操作 $K$ 次：

• 将车移动到与当前占据方格在同一行或同一列的其他方格上。注意，必须移动到与当前方格不同的位置。

在经过 $K$ 次操作后，有多少种方法可以使车最终位于 $(x_2, y_2)$？由于答案可能非常大，请计算结果对 $998244353$ 取模后的值。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a $H \times W$-square grid with $H$ horizontal rows and $W$ vertical columns. Let $(i, j)$ denote the square at the $i$-th row from the top and $j$-th column from the left.

The grid has a rook, initially on $(x_1, y_1)$. Takahashi will do the following operation $K$ times.

• Move the rook to a square that shares the row or column with the square currently occupied by the rook. Here, it must move to a square different from the current one.

How many ways are there to do the $K$ operations so that the rook will be on $(x_2, y_2)$ in the end? Since the answer can be enormous, find it modulo $998244353$.

Constraints

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

Input

Input is given from Standard Input in the following format:

$H$ $W$ $K$

$x_1$ $y_1$ $x_2$ $y_2$

Output

Print the number of ways to do the $K$ operations so that the rook will be on $(x_2, y_2)$ in the end, modulo $998244353$.

Sample Input 1

2 2 2
1 2 2 1

Sample Output 1

2

We have the following two ways.

• First, move the rook from $(1, 2)$ to $(1, 1)$. Second, move it from $(1, 1)$ to $(2, 1)$.
• First, move the rook from $(1, 2)$ to $(2, 2)$. Second, move it from $(2, 2)$ to $(2, 1)$.

Sample Input 2

1000000000 1000000000 1000000
1000000000 1000000000 1000000000 1000000000

Sample Output 2

24922282

Be sure to find the count modulo $998244353$.

Sample Input 3

3 3 3
1 3 3 3

Sample Output 3

9

update @ 2024/3/10 10:07:09