题目描述

有一个纵向 $A$ 行横向 $B$ 列的网格，所有格子初始均为白色。你可以反复进行如下操作：

• 设当前网格为纵向 $a$ 行横向 $b$ 列。你可以选择增加一行或一列。
  • 如果选择增加一行，则在网格顶部增加 $1$ 行，网格变为纵向 $a+1$ 行横向 $b$ 列。
  • 如果选择增加一列，则在网格右侧增加 $1$ 列，网格变为纵向 $a$ 行横向 $b+1$ 列。
• 在每次操作中新增加的格子中，恰好有 $1$ 个格子被涂成黑色，其余新格子保持白色。

最终，若网格变为纵向 $C$ 行横向 $D$ 列，求最终网格所有可能的不同涂色方案数，答案对 $998244353$ 取模。

输入格式

输入为一行，包含四个整数：

$A$ $B$ $C$ $D$

输出格式

输出最终网格所有可能的不同涂色方案数，对 $998244353$ 取模后的结果。

样例 1

输入

1 1 2 2

输出

3

样例 2

输入

2 1 3 4

输出

65

样例 3

输入

31 41 59 265

输出

387222020

说明/提示

限制条件

• $1 \leq A \leq C \leq 3000$
• $1 \leq B \leq D \leq 3000$
• $A,B,C,D$ 均为整数

样例解释 1

除了左下角以外的 $3$ 个格子中，任意 $2$ 个格子被涂成黑色的方案都满足条件。

由 ChatGPT 4.1 翻译