E - Rook Path Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

縦 H 行、横 W 行の H \times 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

以下の 2 通りです。

  • 1 回目の操作でルークをマス (1, 2) からマス (1, 1) へ動かし、2 回目の操作でルークをマス (1, 1) からマス (2, 1) に動かす。
  • 1 回目の操作でルークをマス (1, 2) からマス (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

Score : 500 points

Problem Statement

There is a H \times W-square grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

The grid has a rook, initially on (x_1, y_1). Takahashi will do the following operation K times.

  • Move the rook to a square that shares the row or column with the square currently occupied by the rook. Here, it must move to a square different from the current one.

How many ways are there to do the K operations so that the rook will be on (x_2, y_2) in the end? Since the answer can be enormous, find it modulo 998244353.

Constraints

  • 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

Input

Input is given from Standard Input in the following format:

H W K
x_1 y_1 x_2 y_2

Output

Print the number of ways to do the K operations so that the rook will be on (x_2, y_2) in the end, modulo 998244353.

Sample Input 1

2 2 2
1 2 2 1

Sample Output 1

2

We have the following two ways.

  • First, move the rook from (1, 2) to (1, 1). Second, move it from (1, 1) to (2, 1).
  • First, move the rook from (1, 2) to (2, 2). Second, move it from (2, 2) to (2, 1).

Sample Input 2

1000000000 1000000000 1000000
1000000000 1000000000 1000000000 1000000000

Sample Output 2

24922282

Be sure to find the count modulo 998244353.

Sample Input 3

3 3 3
1 3 3 3

Sample Output 3

9