← 返回题目列表

AtCoder · abc232_e

H. Rook 路径

中文机器翻译题面 查看原题

分数: 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