← 返回题目列表

AtCoder · arc203_c

C. 墙壁的破坏

中文机器翻译题面 查看原题

分数: 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

在第一种情况下,拆除任何单面墙都不允许从左上角的房间移动到右下角的房间。
在第二种情况下,从四堵可用墙中选择并拆除任意三堵墙,即可从左上角的房间移动到右下角的房间。