分数: 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