B - Extension /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600

問題文

A マス横 B マスのマス目があり、そのすべてのマスは白く塗られています。このマス目に、以下の操作を繰り返し行います。

  • 現在のマス目が縦 a マス横 b マスであるとする。縦または横を選ぶ。
    • 縦を選んだ場合はマス目の上に 1 行を追加し、縦 a+1 マス横 b マスのマス目にする。
    • 横を選んだ場合はマス目の右に 1 列を追加し、縦 a マス横 b+1 マスのマス目にする。
  • これにより追加されたマスのうちちょうど 1 マスを黒く塗り、追加された残りのマスを白く塗る。

最終的にマス目が縦 C マス横 D マスになったとするとき、最終的なマス目の異なる塗られ方としてありうるものの個数を 998244353 で割った余りを求めてください。

制約

  • 1 \leq A \leq C \leq 3000
  • 1 \leq B \leq D \leq 3000
  • A,B,C,D は整数である

入力

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

A B C D

出力

最終的なマス目の異なる塗られ方としてありうるものの個数を 998244353 で割った余りを出力せよ。


入力例 1

1 1 2 2

出力例 1

3

左下以外の 3 マスの中の任意の 2 マスが黒く塗られているような塗られ方が条件を満たします。


入力例 2

2 1 3 4

出力例 2

65

入力例 3

31 41 59 265

出力例 3

387222020

Score : 600 points

Problem Statement

We have a grid with A horizontal rows and B vertical columns, with the squares painted white. On this grid, we will repeatedly apply the following operation:

  • Assume that the grid currently has a horizontal rows and b vertical columns. Choose "vertical" or "horizontal".
    • If we choose "vertical", insert one row at the top of the grid, resulting in an (a+1) \times b grid.
    • If we choose "horizontal", insert one column at the right end of the grid, resulting in an a \times (b+1) grid.
  • Then, paint one of the added squares black, and the other squares white.

Assume the grid eventually has C horizontal rows and D vertical columns. Find the number of ways in which the squares can be painted in the end, modulo 998244353.

Constraints

  • 1 \leq A \leq C \leq 3000
  • 1 \leq B \leq D \leq 3000
  • A, B, C, and D are integers.

Input

Input is given from Standard Input in the following format:

A B C D

Output

Print the number of ways in which the squares can be painted in the end, modulo 998244353.


Sample Input 1

1 1 2 2

Sample Output 1

3

Any two of the three squares other than the bottom-left square can be painted black.


Sample Input 2

2 1 3 4

Sample Output 2

65

Sample Input 3

31 41 59 265

Sample Output 3

387222020