AT_arc203_c [ARC203C] Destruction of Walls

縦 $ H $ 行、横 $ W $ 列のグリッド状に部屋が並んでいます。 辺を共有して隣り合う部屋の間には壁があります。 ある部屋 $ A $ にいて、部屋 $ B $ が部屋 $ A $ と **上下左右** のいずれかに隣接し、部屋 $ A $ と部屋 $ B $ の間の壁が取り壊されているとき、部屋 $ A $ から部屋 $ B $ に移動することができます。 以下の条件を満たすような $ K $ 個の壁の組の選び方の総数を $ 998244353 $ で割った余りを求めてください。 - 選んだ壁をすべて取り壊すと、最も左上の部屋からいくつかの部屋を経由して最も右下の部屋に移動することができる。 $ 1 $ つの入力ファイルにつき、 $ T $ 個のテストケースを解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各ケースは以下の形式で与えられる。 > $ H $ $ W $ $ K $

答えを合計 $ T $ 行で出力せよ。 $ t $ 行目には、 $ t $ 番目のテストケースについて条件を満たすような $ K $ 個の壁の組の選び方の総数を $ 998244353 $ で割った余りを出力せよ。

### Sample Explanation 1 $ 1 $ つ目のケースでは、どの $ 1 $ 枚の壁を取り壊しても左上の部屋から右下の部屋に移動することはできません。 $ 2 $ つ目のケースでは、 $ 4 $ 枚ある壁から任意の $ 3 $ 枚を選んで取り壊すと左上の部屋から右下の部屋に移動することができます。 ### 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} $ - 入力される値は全て整数