#arc114e. [arc114_e]Paper Cutting 2

[arc114_e]Paper Cutting 2

Problem Statement

We have a rectangular piece of paper divided into HtimesWH \\times W squares, where two of those squares are painted black and the rest are painted white. If we let (i,j)(i, j) denote the square at the ii-th row and jj-th column, the squares painted black are (h1,w1)(h_1, w_1) and (h2,w2)(h_2, w_2).

Maroon will repeat the following operation to cut the piece of paper:

  • Assume that we have htimeswh \\times w squares remaining. There are (h1)(h - 1) horizontal lines and (w1)(w - 1) vertical lines that are parallel to the edges of the piece and pass the borders of the squares. He chooses one of these lines uniformly at random and cuts the piece into two along that line. Then,
    • if the two black squares are on the same piece, he throws away the other piece and continues the process;
    • otherwise, he ends the process.

Find the expected value of the number of times Maroon cuts a piece of paper until he ends the process, modulo 998244353998244353.

Notes

We can prove that the expected value in question is always a rational number. Additionally, under the constraints of this problem, we can also prove that if we express that value as an irreducible fraction fracPQ\\frac{P}{Q}, we have Qnotequiv0pmod998244353Q \\not \\equiv 0 \\pmod{998244353}. Thus, there exists a unique integer RR such that $R \\times Q \\equiv P \\pmod{998244353}, 0 \\leq R < 998244353$. Answer this RR.

Constraints

  • 1leqH,Wleq1051 \\leq H, W \\leq 10^5
  • HtimesWgeq2H \\times W \\geq 2
  • 1leqh1,h2leqH1 \\leq h_1, h_2 \\leq H
  • 1leqw1,w2leqW1 \\leq w_1, w_2 \\leq W
  • (h1,w1)neq(h2,w2)(h_1, w_1) \\neq (h_2, w_2)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

HH WW h1h_1 w1w_1 h2h_2 w2w_2

Print

Find the expected value of the number of times Maroon cuts a piece of paper until he ends the process, modulo 998244353998244353.


Sample Input 1

2 3
2 2 1 1

Sample Output 1

332748119

In the first cut, the process will end with probability 2/32/3. For the remaining case with probability 1/31/3, the process will end in the second cut.

Thus, the expected number of cuts is 1times2/3+2times1/3=4/31 \\times 2/3 + 2 \\times 1/3 = 4/3.


Sample Input 2

1 5
1 2 1 3

Sample Output 2

332748120

Sample Input 3

2 1
2 1 1 1

Sample Output 3

1

The process will always end in the first cut.


Sample Input 4

10 10
3 4 5 6

Sample Output 4

831078040