{"problem":{"name":"Rook Path","description":{"content":"There is a $H \\times W$\\-square grid with $H$ horizontal rows and $W$ vertical columns. Let $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left. The grid has a ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc232_e"},"statements":[{"statement_type":"Markdown","content":"There is a $H \\times W$\\-square grid with $H$ horizontal rows and $W$ vertical columns. Let $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left.\nThe grid has a rook, initially on $(x_1, y_1)$. Takahashi will do the following operation $K$ times.\n\n*   Move the rook to a square that shares the row or column with the square currently occupied by the rook. Here, it must move to a square different from the current one.\n\nHow many ways are there to do the $K$ operations so that the rook will be on $(x_2, y_2)$ in the end? Since the answer can be enormous, find it modulo $998244353$.\n\n## Constraints\n\n*   $2 \\leq H, W \\leq 10^9$\n*   $1 \\leq K \\leq 10^6$\n*   $1 \\leq x_1, x_2 \\leq H$\n*   $1 \\leq y_1, y_2 \\leq W$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$H$ $W$ $K$\n$x_1$ $y_1$ $x_2$ $y_2$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc232_e","tags":[],"sample_group":[["2 2 2\n1 2 2 1","2\n\nWe have the following two ways.\n\n*   First, move the rook from $(1, 2)$ to $(1, 1)$. Second, move it from $(1, 1)$ to $(2, 1)$.\n*   First, move the rook from $(1, 2)$ to $(2, 2)$. Second, move it from $(2, 2)$ to $(2, 1)$."],["1000000000 1000000000 1000000\n1000000000 1000000000 1000000000 1000000000","24922282\n\nBe sure to find the count modulo $998244353$."],["3 3 3\n1 3 3 3","9"]],"created_at":"2026-03-03 11:01:14"}}