E - Snuke's Kyoto Trip Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 800 点

問題文

整数 W,H,L,R,D,U が与えられます。

2 次元平面上に京都の町があります。

京都の町には、以下の条件をすべて満たす格子点 (x,y) に 1 つずつ区画が存在します。それ以外の点に区画はありません。

  • 0\leq x\leq W
  • 0\leq y\leq H
  • x\lt L または R\lt x または y\lt D または U\lt y

すぬけくんは、以下のように京都の町を旅しました。

  • まず、区画を 1 つ選んでそこに立つ。
  • その後、0 回以上好きな回数以下の操作を行う。
    • x 軸正方向または y 軸正方向に 1 移動する。ただし、移動後の点にも区画がなくてはならない。

すぬけくんが通った経路としてあり得るものの個数を 998244353 で割った余りを求めてください。

制約

  • 0\leq L\leq R\leq W\leq 10^6
  • 0\leq D\leq U\leq H\leq 10^6
  • 区画が 1 つ以上存在する
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

W H L R D U

出力

答えを出力せよ。

入力例 1

4 3 1 2 2 3

出力例 1

192

以下のような経路が考えられます。ここで、経路は通った格子点を順に並べることで表しています。

  • (3,0)
  • (0,0)\rightarrow (1,0)\rightarrow (2,0)\rightarrow (2,1)\rightarrow (3,1)\rightarrow (3,2)\rightarrow (4,2)\rightarrow (4,3)
  • (0,1)\rightarrow (0,2)

考えられる経路の個数は 192 個です。

入力例 2

10 12 4 6 8 11

出力例 2

4519189

入力例 3

192 25 0 2 0 9

出力例 3

675935675

経路の個数を 998244353 で割った余りを求めることを忘れないでください。

Score : 800 points

Problem Statement

You are given integers W,H,L,R,D,U.

A town of Kyoto is on the two-dimensional plane.

In the town, there is exactly one block at each lattice point (x,y) that satisfies all of the following conditions. There are no blocks at any other points.

  • 0\leq x\leq W
  • 0\leq y\leq H
  • x<L or R<x or y<D or U<y

Snuke traveled through the town as follows.

  • First, he chooses one block and stands there.
  • Then, he performs the following operation any number of times (possibly zero):
    • Move one unit in the positive direction of the x-axis or the positive direction of the y-axis. However, the point after moving must also have a block.

Print the number, modulo 998244353, of possible paths that Snuke could have taken.

Constraints

  • 0\leq L\leq R\leq W\leq 10^6
  • 0\leq D\leq U\leq H\leq 10^6
  • There is at least one block.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

W H L R D U

Output

Print the answer.

Sample Input 1

4 3 1 2 2 3

Sample Output 1

192

The following are examples of possible paths. Here, a path is represented by listing the lattice points visited in order.

  • (3,0)
  • (0,0)\rightarrow (1,0)\rightarrow (2,0)\rightarrow (2,1)\rightarrow (3,1)\rightarrow (3,2)\rightarrow (4,2)\rightarrow (4,3)
  • (0,1)\rightarrow (0,2)

There are 192 possible paths.

Sample Input 2

10 12 4 6 8 11

Sample Output 2

4519189

Sample Input 3

192 25 0 2 0 9

Sample Output 3

675935675

Do not forget to print the number of paths modulo 998244353.