配点 : $600$ 点

問題文

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

• 現在のマス目が縦 $a$ マス横 $b$ マスであるとする。縦または横を選ぶ。- 縦を選んだ場合はマス目の上に $1$ 行を追加し、縦 $a+1$ マス横 $b$ マスのマス目にする。
  • 横を選んだ場合はマス目の右に $1$ 列を追加し、縦 $a$ マス横 $b+1$ マスのマス目にする。
• 縦を選んだ場合はマス目の上に $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 2 2

3

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

2 1 3 4

65

31 41 59 265

387222020