AT_arc202_d [ARC202D] King

縦 $ 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 $ 回目の操作を終了した時点での王将があるマスが異なる場合に異なるとみなします。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ T $ $ A $ $ B $ $ C $ $ D $

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

### Sample Explanation 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) $ ### 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 $ - 入力される値は全て整数