AT_arc203_c.[ARC203C] Destruction of Walls

有一个由 $H$ 行 $W$ 列组成的网格状房间。每两个共享边的相邻房间之间都有一堵墙。
如果你在房间 $A$，房间 $B$ 与房间 $A$ 在上下左右方向上相邻，并且 $A$ 与 $B$ 之间的墙被拆除，则你可以从房间 $A$ 移动到房间 $B$。

请计算满足以下条件的 $K$ 面墙的组合的总数，并将答案对 $998244353$ 取模：

• 拆除选中的所有墙后，可以从最左上角的房间经过若干房间移动到最右下角的房间。

对于每个输入文件，需要解答 $T$ 个测试用例。

输入通过标准输入给出，格式如下：

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

每个测试用例的格式如下：

$H$ $W$ $K$

请输出共 $T$ 行答案。第 $t$ 行输出第 $t$ 个测试用例满足条件的 $K$ 面墙组合数对 $998244353$ 取模的结果。

限制条件

• $1 \leq T \leq 2 \times 10^5$
• $2 \leq H \leq 2 \times 10^5$
• $2 \leq W \leq 2 \times 10^5$
• $0 \leq K \leq H+W$
• 输入的所有值均为整数

样例解释 1

对于第 $1$ 个测试用例，无论拆除哪一面墙，都无法从左上角房间移动到右下角房间。对于第 $2$ 个测试用例，从 $4$ 面墙中任意选择 $3$ 面拆除后，可以从左上角房间移动到右下角房间。

由 ChatGPT 4.1 翻译