102324: [AtCoder]ABC232 E - Rook Path

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:6 Solved:0

Description

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

Input

题意翻译

有一个 $H\times W$ 的国际象棋棋盘,求一个**车**从 $(x_1,y_1)$ 走到 $(x_2,y_2)$ 正好用 $K$ 步的方案数。 Translated by @[$\tt{\_YXJS\_}$](/user/516346).

Output

得分: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)$移动到$(1, 1)$。其次,将它从$(1, 1)$移动到$(2, 1)$。
  • 首先,将车从$(1, 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

加入题单

上一题 下一题 算法标签: