/ 
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