C - Destruction of Walls 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 600 点

問題文

縦 H 行、横 W 列のグリッド状に部屋が並んでいます。 辺を共有して隣り合う部屋の間には壁があります。
ある部屋 A にいて、部屋 B が部屋 A と 上下左右 のいずれかに隣接し、部屋 A と部屋 B の間の壁が取り壊されているとき、部屋 A から部屋 B に移動することができます。

以下の条件を満たすような K 個の壁の組の選び方の総数を 998244353 で割った余りを求めてください。

  • 選んだ壁をすべて取り壊すと、最も左上の部屋からいくつかの部屋を経由して最も右下の部屋に移動することができる。

1 つの入力ファイルにつき、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 行目には、t 番目のテストケースについて条件を満たすような K 個の壁の組の選び方の総数を 998244353 で割った余りを出力せよ。

入力例 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

1 つ目のケースでは、どの 1 枚の壁を取り壊しても左上の部屋から右下の部屋に移動することはできません。
2 つ目のケースでは、4 枚ある壁から任意の 3 枚を選んで取り壊すと左上の部屋から右下の部屋に移動することができます。

Score : 600 points

Problem Statement

Rooms are arranged in a grid with H rows and W columns. There are walls between adjacent rooms that share an edge.
When you are in room A and room B is adjacent to room A in one of the four directions (up, down, left, right), and the wall between room A and room B has been demolished, you can move from room A to room B.

Find the total number, modulo 998244353, of ways to choose K walls such that the following condition is satisfied.

  • When all chosen walls are demolished, it is possible to move from the top-left room to the bottom-right room by passing through some rooms.

Solve T test cases for each input file.

Constraints

  • 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}
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each case is given in the following format:

H W K

Output

Output the answers in a total of T lines. The t-th line should contain the total number, modulo 998244353, of ways to select K walls that satisfy the condition for the t-th test case.

Sample Input 1

6
2 2 1
2 2 3
2 2 2
2 2 4
200000 200000 400000
2 203 203

Sample Output 1

0
4
2
1
387815582
203

In the first case, demolishing any single wall does not allow movement from the top-left room to the bottom-right room.
In the second case, choosing and demolishing any three walls out of the four available walls allows movement from the top-left room to the bottom-right room.