{"raw_statement":[{"iden":"problem statement","content":"Rooms are arranged in a grid with $H$ rows and $W$ columns. There are walls between adjacent rooms that share an edge.  \nWhen 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$.\nFind the total number, modulo $998244353$, of ways to choose $K$ walls such that the following condition is satisfied.\n\n*   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.\n\nSolve $T$ test cases for each input file."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 2 \\times 10^5$\n*   $2 \\leq H \\leq 2 \\times 10^5$\n*   $2 \\leq W \\leq 2 \\times 10^5$\n*   $\\boldsymbol{0 \\leq K \\leq H+W}$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach case is given in the following format:\n\n$H$ $W$ $K$"},{"iden":"sample input 1","content":"6\n2 2 1\n2 2 3\n2 2 2\n2 2 4\n200000 200000 400000\n2 203 203"},{"iden":"sample output 1","content":"0\n4\n2\n1\n387815582\n203\n\nIn the first case, demolishing any single wall does not allow movement from the top-left room to the bottom-right room.  \nIn 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."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}