seuOJ405 - Far Away Light

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：春季, 夏季, 校赛, 2022

题目描述

Arcaea世界充满了不可能。虽然她已经学到了不少，但是仍然还有很多她不了解的事情。 还有许多尚待解决的疑问。

拉格兰发现自己又一次陷入了虚无。

她朝前走去。

她放开卫星，于是卫星停留在她的肩头。

他们欣赏着沿途发出亮光的云朵并朝着Arcaea行进。

……直到其中一朵引起她的注意。

在一个$n\times m$的格点图上，有一朵云在移动。每个时刻，它会从当前格点移动到同一行或同一列的另一个格点上，但它不会在原地停留。拉格兰知道起始时这朵云的位置$(x_1,y_1)$，她想让这朵云在$k$个时刻后，到达她给定的位置$(x_2,y_2)$。你想知道有多少种方案能满足她的愿望。

格点图的左上角的坐标是$(1,1)$，右下角的坐标是$(n,m)$。

由于答案可能很大，你应当输出对$998244353$取模后的方案数。

对于任意两个方案，如果在某个时刻存在云的位置不同，则这两个方案视为不同的方案。

输入格式

输入的第一行有三个整数，分别代表格点图的大小$n,m(2\leq n,m\leq 10^{18})$和时刻数$k(1\leq k \leq 10^{18})$。

第二行有两个整数，代表起始时云的位置坐标$(x_1,y_1)(1\leq x_1 \leq n,1\leq y_1 \leq m)$。

第三行有两个整数，代表$k$个时刻后拉格兰想要到达的位置坐标$(x_2,y_2)(1\leq x_2 \leq n,1\leq y_2 \leq m)$。

输出格式

输出一行一个整数，代表对 $998244353$ 取模后的方案数。

样例

样例输入1

2 4 3
1 4
2 1

样例输出1

6

样例解释1

方案$1$：$(1,4)\rightarrow(1,3)\rightarrow(1, 1)\rightarrow(2,1)$

方案$2$：$(1,4)\rightarrow(1,2)\rightarrow(1, 1)\rightarrow(2,1)$

方案$3$：$(1,4)\rightarrow(1,3)\rightarrow(2, 3)\rightarrow(2,1)$

方案$4$：$(1,4)\rightarrow(1,2)\rightarrow(2, 2)\rightarrow(2,1)$

方案$5$：$(1,4)\rightarrow(2,4)\rightarrow(2, 3)\rightarrow(2,1)$

方案$6$：$(1,4)\rightarrow(2,4)\rightarrow(2, 2)\rightarrow(2,1)$

样例输入2

2 2 2
1 1
1 1

样例输出2

2

样例解释2

方案$1$：$(1,1)\rightarrow(1,2)\rightarrow(1,1)$

方案$2$：$(1,1)\rightarrow(2,1)\rightarrow(1,1)$

样例输入3

100000000000000000 100000000000000000 100000000000000000
1 1
100000000000000000 100000000000000000

样例输出3

562897480

样例解释3

$100000000000000000=10^{17}$