{"problem":{"name":"Destruction of Walls","description":{"content":"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 fou","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc203_c"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc203_c","tags":[],"sample_group":[["6\n2 2 1\n2 2 3\n2 2 2\n2 2 4\n200000 200000 400000\n2 203 203","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."]],"created_at":"2026-03-03 11:01:14"}}