Call the region defined by \(L\leq x\leq R\) and \(D\leq y\leq U\) the forbidden region.

Furthermore, we will frequently ignore the rule that one cannot pass through the forbidden region, and in the end we will count only those paths that do not pass through it.

We accept the following two equalities for non-negative \(H\) and \(W\). (The proofs here are obtained by repeatedly transforming the equations after accepting the hockey-stick identity.)

---

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

This is equal to the number of paths when there is no forbidden region and the starting block is at \((0,0)\).

Proof

$$ \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\]

This is equal to the number of paths when there is no forbidden region.

Proof

$$ \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} $$

---

From now on, let us denote \(\text{bs}(x,y)=\binom{x+y+2}{x+1}-1\) and \(\text{bss}(x,y)=\binom{x+y+4}{x+2}-(x+2)(y+2)-1\). These expressions are equal to the right-hand sides of the equations above.

The desired answer is equal to the number of paths when there is no forbidden region minus the number of paths that pass through the forbidden region.
The paths that pass through the forbidden region can be divided into three types:

• Paths that start and end within the forbidden region.
• Paths that start outside the forbidden region but pass through it.
• Paths that start within the forbidden region but end outside it.

When there is no forbidden region, the total number of paths is \(\text{bss}(H,W)\).

The number of paths that both start and end within the forbidden region is \(\text{bss}(R-L,U-D)\).

Now, consider the paths that start outside the forbidden region and pass through it. Let \((x_1,y_1)\) be the last point outside the forbidden region before entering the forbidden region, and \((x_2,y_2)\) be the first point inside the forbidden region. Then the number of such paths is given by \(\text{bs}(x_1,y_1)\times \text{bs}(W-x_2,H-y_2)\).

The number of pairs \(((x_1,y_1),(x_2,y_2))\) is only \(O((R-L)+(U-D))\), and since different pairs count different paths, one may simply iterate over all such pairs and take the sum.

The case of paths that start within the forbidden region and end outside it can be handled in a similar manner. Let \((x_1,y_1)\) be the last point within the forbidden region and \((x_2,y_2)\) be the first point outside it; then the number of such paths is \(\text{bs}(x_1-L,y_1-D)\times \text{bs}(W-x_2,H-y_2)\). Again, by iterating over all such pairs along the boundary, the total count can be computed.

By precomputing factorials for \(O(W+H)\) numbers to compute binomial coefficients, all required values can be computed in \(O(W+H)\) time.

---

As an aside, the two equalities stated at the beginning can also be proved combinatorially (the writer discovered the equalities using this approach).

The first equality is shown by establishing a one-to-one correspondence between almost all paths from \((0,0)\) to \((W+1,H+1)\) and the counted paths.

The second equality is shown by establishing a one-to-one correspondence between almost all paths from \((-1,-1)\) to \((W+1,H+1)\) and the counted paths.

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