King

AtCoder

IDarc202_d

Time15000ms

Memory256MB

Difficulty—

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)$. Initially, the king is placed at $(A, B)$. You perform the following operation exactly $T$ times. * 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. Find 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. ## Constraints * $2 \leq H \leq 3 \times 10^5$ * $2 \leq W \leq 3 \times 10^5$ * $1 \leq T \leq 3 \times 10^5$ * $1 \leq A \leq H$ * $1 \leq B \leq W$ * $1 \leq C \leq H$ * $1 \leq D \leq W$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $H$ $W$ $T$ $A$ $B$ $C$ $D$ [samples]

Samples

Input #1

3 4 3 2 1 3 4

Output #1

5

There are five operation sequences that satisfy the conditions in the problem statement. The king's movements corresponding to each operation sequence are as follows.

*   $(2, 1) \to (1, 2) \to (2, 3) \to (3, 4)$
*   $(2, 1) \to (2, 2) \to (2, 3) \to (3, 4)$
*   $(2, 1) \to (2, 2) \to (3, 3) \to (3, 4)$
*   $(2, 1) \to (3, 2) \to (2, 3) \to (3, 4)$
*   $(2, 1) \to (3, 2) \to (3, 3) \to (3, 4)$

Input #2

202 123 456 20 25 7 20

Output #2

167373259

API Response (JSON)

{
  "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 $(...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments