车的路径

题目描述

有一个由 $H$ 个横向行、$W$ 个纵向列组成的 $H \times W$ 方格网格。用 $(i, j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。

网格上有一枚车(rook),最初位于 $(x_1, y_1)$。高桥君将进行下面的操作 $K$ 次。

将车移动到与车当前所在格子同行或同列的某个格子。此时,必须移动到与当前格子不同的格子。

求使得操作结束后车位于 $(x_2, y_2)$ 的操作方法有多少种。由于答案可能十分巨大,请对 $998244353$ 取模输出。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出使 $K$ 次操作结束后车位于 $(x_2, y_2)$ 的操作方法数对 $998244353$ 取模的值。

样例

2 2 2
1 2 2 1

2

有以下两种方法。

第一种:第一次把车从 $(1, 2)$ 移到 $(1, 1)$;第二次把它从 $(1, 1)$ 移到 $(2, 1)$。

第二种:第一次把车从 $(1, 2)$ 移到 $(2, 2)$;第二次把它从 $(2, 2)$ 移到 $(2, 1)$。

1000000000 1000000000 1000000
1000000000 1000000000 1000000000 1000000000

24922282

请务必对 $998244353$ 取模后输出。

3 3 3
1 3 3 3

9

数据范围

• $2 \le H, W \le 10^9$
• $1 \le K \le 10^6$
• $1 \le x_1, x_2 \le H$
• $1 \le y_1, y_2 \le W$
• 输入均为整数