分数: 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.
示例输入 1
2 2 2 1 2 2 1
示例输出 1
2
我们有以下两种方式。
- 首先,将车从 (1, 2) to (1, 1)。其次,将其从 (1, 1) to (2, 1).
- 首先,将车从 (1, 2) to (2, 2)。其次,将其从 (2, 2) to (2, 1).
示例输入 2
1000000000 1000000000 1000000 1000000000 1000000000 1000000000 1000000000
示例输出 2
24922282
一定要找到计数模数 998244353.
示例输入 3
3 3 3 1 3 3 3
示例输出 3
9