{"problem":{"name":"King","description":{"content":"There is a shogi (Japanese chess) board with $H$ rows and $W$ columns, and one king piece. The square at the $i$\\-th row from the top and $j$\\-th column from the left of the board is represented as $(","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":15000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc202_d"},"statements":[{"statement_type":"Markdown","content":"There is a shogi (Japanese chess) board with $H$ rows and $W$ columns, and one king piece. The square at the $i$\\-th row from the top and $j$\\-th column from the left of the board is represented as $(i, j)$.  \nInitially, the king is placed at $(A, B)$. You perform the following operation exactly $T$ times.\n\n*   Move the king to one of the eight adjacent squares of the current square. More precisely, if the king is at square $(i, j)$, move the king to one of $(i+1,j+1), (i+1,j), (i+1,j-1), (i,j+1), (i,j-1), (i-1,j+1), (i-1,j), (i-1,j-1)$. The king cannot leave the board.\n\nFind the number, modulo $998244353$, of operation sequences such that the king is at $(C, D)$ after completing all $T$ operations. Two operation sequences are considered different if and only if there exists an integer $i$ $(1 \\leq i \\leq T)$ such that the king's position after the $i$\\-th operation is different.\n\n## Constraints\n\n*   $2 \\leq H \\leq 3 \\times 10^5$\n*   $2 \\leq W \\leq 3 \\times 10^5$\n*   $1 \\leq T \\leq 3 \\times 10^5$\n*   $1 \\leq A \\leq H$\n*   $1 \\leq B \\leq W$\n*   $1 \\leq C \\leq H$\n*   $1 \\leq D \\leq W$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$H$ $W$ $T$ $A$ $B$ $C$ $D$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc202_d","tags":[],"sample_group":[["3 4 3 2 1 3 4","5\n\nThere are five operation sequences that satisfy the conditions in the problem statement. The king's movements corresponding to each operation sequence are as follows.\n\n*   $(2, 1) \\to (1, 2) \\to (2, 3) \\to (3, 4)$\n*   $(2, 1) \\to (2, 2) \\to (2, 3) \\to (3, 4)$\n*   $(2, 1) \\to (2, 2) \\to (3, 3) \\to (3, 4)$\n*   $(2, 1) \\to (3, 2) \\to (2, 3) \\to (3, 4)$\n*   $(2, 1) \\to (3, 2) \\to (3, 3) \\to (3, 4)$"],["202 123 456 20 25 7 20","167373259"]],"created_at":"2026-03-03 11:01:14"}}