Description

有一个 $H \times W$ 个正方形网格，横向有 $H$ 行，纵向有 $W$ 列。让 $(i, j)$ 表示从上往下第 $i$ 行和从左往上第 $j$ 列的正方形。

网格中有一个车，最初位于 $(x_1, y_1)$ 。高桥将进行以下操作 $K$ 次。

• 将车移动到与车当前所占位置同行或同列的位置。在这里，它必须移动到与当前位置不同的位置。

有多少种方法可以进行 $K$ 次操作以使车最终位于 $(x_2, y_2)$ ？由于答案可能非常庞大，请求取 $998244353$ 的模。

Format

Input

第一行输入三个空格隔开的整数 $H,W,K$

接下来输入四个空格隔开的整数 $x_1,y_1,x_2,y_2$

Output

打印 $K$ 种操作方法的数目，以使车最终位于 $(x_2, y_2)$ 上，模数为 $998244353$ 。

Samples

2 2 2
1 2 2 1

2

1000000000 1000000000 1000000
1000000000 1000000000 1000000000 1000000000

2492282

3 3 3
1 3 3 3

9

样例 1 解释

我们有以下两种方法。

• 首先，将车从 $(1, 2)$ 移动到 $(1, 1)$ 。第二种，将车从 $(1, 1)$ 移动到 $(2, 1)$ 。
• 首先，将车从 $(1, 2)$ 移动到 $(2, 2)$ 。其次，将车从 $(2, 2)$ 移动到 $(2, 1)$ 。

Limitation

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