当前没有测试数据。

E - 附魔塔征程

得分：500

问题描述

有一个 $H \times W$ 格的网格，其中 $H$ 行 $W$ 列。设 $(i, j)$ 表示网格中第 $i$ 行第 $j$ 列的格子。

网格上有一个战车，初始位置在 $(x_1, y_1)$ 处。高橋将进行下列的操作 $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$

输出

输出将战车移动 $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

记得对结果取模 $998244353$。