分数: 600 点
问题陈述
房间按网格排列, H 行和 W 列。
相邻房间之间有共享边缘的墙壁。
当您在房间时 A 和房间 B 毗邻房间 A 四个方向之一 (上、下、左、右),和房间之间的墙壁 A 和房间 B 已拆除,可以搬出房间 A 到房间 B.
求总数,取模 998244353,多种选择 K 墙,以满足以下条件。
- 当所有选定的墙壁被拆除后,可以通过一些房间从左上房间移动到右下房间。
解决 输入文件中的 T 每个输入文件的测试用例。
约束
- 1 \leq T \leq 2 \times 10^5
- 2 \leq H \leq 2 \times 10^5
- 2 \leq W \leq 2 \times 10^5
- \boldsymbol{0 \leq K \leq H+W}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个案例均按以下格式给出:
H W K
输出
总共输出答案 T 行。 的 t- 第行应包含总数,模数 998244353,选择方式 K 满足条件的墙壁 t- 第一个测试用例。
样本输入 1
6 2 2 1 2 2 3 2 2 2 2 2 4 200000 200000 400000 2 203 203
示例输出 1
0 4 2 1 387815582 203
在第一种情况下,拆除任何单面墙都不允许从左上角的房间移动到右下角的房间。
在第二种情况下,从四堵可用墙中选择并拆除任意三堵墙,即可从左上角的房间移动到右下角的房间。