AT_arc203_c [ARC203C] Destruction of Walls

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.

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 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 Explanation 1 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. ### 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.