D - King Editorial /

Time Limit: 15 sec / Memory Limit: 1024 MiB

配点 : 1000 点

問題文

縦 H マス、横 W マスの将棋盤と 1 個の王将の駒があります。将棋盤の上から i 行目、左から j 列目にあるマスを (i, j) と表します。
はじめ、王将は (A, B) に置かれています。あなたは次の操作をちょうど T 回行います。

  • 王将を現在あるマスの 8 近傍のマスに動かす。厳密に言うと、王将があるマスを (i, j) としたとき、(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) のいずれかに王将を動かす。ただし、盤の外に出るような移動はできない。

T 回の操作を全て終了した時点で王将が (C, D) にあるような操作列の個数を 998244353 で割った余りを求めてください。ただし、2 つの操作列はある整数 i (1 \leq i \leq T) が存在して i 回目の操作を終了した時点での王将があるマスが異なる場合に異なるとみなします。

制約

  • 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
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

H W T A B C D

出力

T 回の操作を全て終了した時点で王将が (C, D) にあるような操作列の個数を 998244353 で割った余りを出力せよ。

入力例 1

3 4 3 2 1 3 4

出力例 1

5

問題文の条件を満たす操作列は全部で 5 個あります。各操作列に対応する王将の移動は次の通りです。

  • (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)

入力例 2

202 123 456 20 25 7 20

出力例 2

167373259

Score : 1000 points

Problem Statement

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

Output

Output the number, modulo 998244353, of operation sequences such that the king is at (C, D) after completing all T operations.

Sample Input 1

3 4 3 2 1 3 4

Sample 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)

Sample Input 2

202 123 456 20 25 7 20

Sample Output 2

167373259