← 返回题目列表

AtCoder · arc202_d

D. 王

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

有一个将棋(日本象棋)棋盘,上面有 H 行和 W 列,以及一张国王棋子。广场位于 i从顶部开始的第行和 j板左侧的第列表示为 (i, j).
最初,国王被放置在 (A, B)。您准确执行以下操作 T 次。

  • 将国王移至当前方格的八个相邻方格之一。更准确地说,如果国王处于方格状态 (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)。国王不能离开棋盘。

求模数 998244353,使得国王处于 (C, D) 完成所有操作后 T 操作。当且仅当存在一个整数时,两个操作序列被认为是不同的 i (1 \leq i \leq T) 这样国王的位置就在 i-th 操作不同。

约束

  • 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

输出

输出数字,模数 998244353,使得国王处于 (C, D) 完成所有操作后 T 操作。


示例输入 1

3 4 3 2 1 3 4

示例输出 1

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