题目描述

有一个 $H \times W$ 的方格网格，其中有 $H$ 行和 $W$ 列。用 $(i, j)$ 表示从上往下数第 $i$ 行、从左往右数第 $j$ 列的方格。

方格网格里有一个车（rook），初始位置为 $(x_1, y_1)$。Takahashi 将执行以下操作 $K$ 次：

• 将车移动到与其当前所在的方格共行或共列的方格上。换句话说，车只能沿着行或列移动，但不能留在原方格。

有多少种方法可以进行这 $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$

输入

从标准输入读入数据，输入格式如下：

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

输出

输出答案，即使得车最后停在 $(x_2, y_2)$ 位置的方法数，对 $998244353$ 取模。

示例输入1

2 2 2
1 2 2 1

示例输出1

2

有以下两种方法：

• 第一步，车从 $(1, 2)$ 移动到 $(1, 1)$；第二步，车从 $(1, 1)$ 移动到 $(2, 1)$。
• 第一步，车从 $(1, 2)$ 移动到 $(2, 2)$；第二步，车从 $(2, 2)$ 移动到 $(2, 1)$。

示例输入2

1000000000 1000000000 1000000
1000000000 1000000000 1000000000 1000000000

示例输出2

24922282

请确保对 $998244353$ 取模。

示例输入3

3 3 3
1 3 3 3

示例输出3

9