\(L\leq x\leq R\) かつ \(D\leq y\leq U\) なる領域を 禁止領域 と呼びます。

また、しばしば禁止領域内を通れないルールを無視します。最終的に禁止領域内を通らないものだけをうまく数えるようにします。

次の \(2\) つの等式が \(0\leq H,W\) のときに成り立つことを認めます。ここでの証明はホッケースティック恒等式を認めたのちに式変形を繰り返すものです。

---

\[\displaystyle \sum_{x=0}^{W}\sum_{y=0}^{H}\binom{x+y}{x}=\binom{W+H+2}{W+1}-1\]

これは、禁止領域が存在しない、かつはじめに選ぶ区画の位置が \((0,0)\) の場合の通り数と等しいです。

証明

$$ \begin{aligned} \displaystyle \sum_{x=0}^{W}\sum_{y=0}^{H}\binom{x+y}{x}&=\displaystyle \sum_{x=0}^{W}\sum_{y=x}^{x+H}\binom{y}{x}\\ &=\displaystyle \sum_{x=0}^{W}\binom{x+H+1}{x+1}\\ &=\displaystyle \sum_{x=1}^{W+1}\binom{x+H}{x}\\ &=\displaystyle \sum_{x=1}^{W+1}\binom{x+H}{H}\\ &=\displaystyle \sum_{x=H+1}^{W+H+1}\binom{x}{H}\\ &=\displaystyle \sum_{x=H}^{W+H+1}\binom{x}{H}-\binom{H}{H}\\ &=\binom{W+H+2}{H+1}-1 \end{aligned} $$

---

\[\displaystyle \sum_{x_1=0}^{W}\sum_{y_1=0}^{H}\sum_{x_2=x_1}^{W}\sum_{y_2=y_1}^{H}\binom{(x_2-x_1)+(y_2-y_1)}{x_2-x_1}=\binom{W+H+4}{W+2}-(W+2)(H+2)-1\]

これは、禁止領域が存在しない場合の通り数と等しいです。

証明

$$ \begin{aligned} \sum_{x_1=0}^{W}\sum_{y_1=0}^{H}\sum_{x_2=x_1}^{W}\sum_{y_2=y_1}^{H}\binom{(x_2-x_1)+(y_2-y_1)}{x_2-x_1} &=\sum_{x_1=0}^{W}\sum_{y_1=0}^{H}\sum_{x_2=0}^{W-x_1}\sum_{y_2=0}^{H-y_1}\binom{x_2+y_2}{x_2}\\ &=\sum_{x=0}^{W}\sum_{y=0}^{H}\left\lbrace\binom{(W-x)+(H-y)+2}{W-x+1}-1\right\rbrace\\ &=\sum_{x=0}^{W}\sum_{y=0}^{H}\binom{(W-x)+(H-y)+2}{W-x+1}-(W+1)(H+1)\\ &=\sum_{x=1}^{W+1}\sum_{y=1}^{H+1}\binom{x+y}{x}-(W+1)(H+1)\\ &=\sum_{x=0}^{W+1}\sum_{y=0}^{H+1}\binom{x+y}{x}-\sum_{x=0}^{W+1}\binom{x}{x}-\sum_{y=0}^{H+1}\binom{y}{0}+\binom{0}{0}-(W+1)(H+1)\\ &=\binom{W+H+4}{W+2}-1-(W+2)-(H+2)+1-(W+1)(H+1)\\ &=\binom{W+H+4}{W+2}-(W+1)(H+1)-(W+1)-(H+1)-2\\ &=\binom{W+H+4}{W+2}-(W+2)(H+2)-1\\ \end{aligned} $$

---

以降、\(\displaystyle \text{bs}(x,y)=\binom{x+y+2}{x+1}-1\)、\(\displaystyle \text{bss}(x,y)=\binom{x+y+4}{x+2}-(x+2)(y+2)-1\) とします。これらは先ほどの等式の右辺と等しいです。

求める答えは、禁止領域が存在しない場合の答えから禁止領域を通る経路の個数を引いたものに等しいです。禁止領域を通る経路は、以下の \(3\) つに分けることができます。

• 禁止領域内で始まって禁止領域内で終わる
• 禁止領域外で始まって禁止領域内を通る
• 禁止領域内で始まって禁止領域外で終わる

禁止領域が存在しない場合の答えは \(\text{bss}(H,W)\) です。

禁止領域内で始まって禁止領域内で終わる通り数は \(\text{bss}(R-L,U-D)\) です。

禁止領域外で始まって禁止領域内を通る場合を考えます。最初に通る禁止領域内の点の一個前の点を \((x_1,y_1)\) とし、最初に通る禁止領域内の点を \((x_2,y_2)\) とします。すると、このような通り数は \(\text{bs}(x_1,y_1)\times \text{bs}(W-x_2,H-x_2)\) となります。

\(((x_1,y_1),(x_2,y_2))\) の組は禁止領域の外周の \(O((R-L)+(U-D))\) 個しか存在せず、また組が違えば数える経路も異なるので、全探索して総和を取ればよいです。

禁止領域内で始まって禁止領域外で終わる場合もほぼ同じようにすればよいです。最後に通る禁止領域内の点を \((x_1,y_1)\) とし、最初に通る禁止領域外の点を \((x_2,y_2)\) とすると、このような通り数は \(\text{bs}(x_1-L,y_1-D)\times \text{bs}(W-x_2,H-x_2)\) となります。先ほどと同じように \(((x_1,y_1),(x_2,y_2))\) を全探索すればよいです。

二項係数を求めるために \(O(W+H)\) 個の階乗を前計算しておくことで、すべての必要な値を \(O(W+H)\) 時間で求めることができました。

---

余談ですが、冒頭で認めた \(2\) つの等式は、詳細は略しますが組合せ的な証明も可能です。(Writerはこの方針で等式を発見しました)

前者の等式は、数える経路を \((0,0)\) から \((W+1,H+1)\) に向かう経路のほとんどと一対一対応させることで示せます。

後者の等式は、数える経路を \((-1,-1)\) から \((W+1,H+1)\) に向かう経路のほとんどと一対一対応させることで示せます。

実装例 (PyPy3)

class BinomialTable:
    def __init__(self, table_size):
        self.fact = [1] * table_size
        self.inv = [1] * table_size

        for i in range(1, table_size):
            self.fact[i] = self.fact[i - 1] * i % MOD
        self.inv[-1] = pow(self.fact[-1], -1, MOD)
        for i in reversed(range(1, table_size)):
            self.inv[i - 1] = self.inv[i] * i % MOD

    def binom(self, h, w):
        if h < 0 or w < 0:
            return 0
        return (self.fact[h + w] * self.inv[h] % MOD * self.inv[w]) % MOD

    def binom_sum(self, h, w):
        if h < 0 or w < 0:
            return 0
        return (self.binom(h + 1, w + 1) - 1) % MOD

    def binom_sum_sum(self, h, w):
        if h < 0 or w < 0:
            return 0
        return (self.binom(h + 2, w + 2) - (h + 2) * (w + 2) - 1) % MOD


MOD = 998244353
table = BinomialTable(3000000)

W, H, L, R, D, U = map(int, input().split())
ans = (table.binom_sum_sum(W, H) - table.binom_sum_sum(R - L, U - D)) % MOD

for i in range(D, U + 1):
    ans -= table.binom_sum(L - 1, i) * table.binom_sum(W - L, H - i)
    ans %= MOD

for i in range(L, R + 1):
    ans -= table.binom_sum(i, D - 1) * table.binom_sum(W - i, H - D)
    ans %= MOD

for i in range(D, U + 1):
    ans -= table.binom_sum(R - L, i - D) * table.binom_sum(W - R - 1, H - i)
    ans %= MOD

for i in range(L, R + 1):
    ans -= table.binom_sum(i - L, U - D) * table.binom_sum(W - i, H - U - 1)
    ans %= MOD

print(ans % MOD)