Rook Path

题目描述

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.

将车移动到与当前占据的格子同一行或同一列的某个格子。这里，必须移动到与当前格子不同的格子。

有多少种方法进行这 $K$ 次操作，使得最后车会在 $(x_2, y_2)$？由于答案可能非常大，请对 $998244353$ 取模。

输入格式

Input is given from Standard Input in the following format: $H$ $W$ $K$ $x_1$ $y_1$ $x_2$ $y_2$

输出格式

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

2 2 2
1 2 2 1

2

1000000000 1000000000 1000000
1000000000 1000000000 1000000000 1000000000

24922282

3 3 3
1 3 3 3

9

提示

$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$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)$.
Be sure to find the count modulo $998244353$.

标签: AtCoder|abc232E

来源

AtCoder|abc232E