分数: 600 点
问题陈述
我们有一个网格 A 水平行和 B 垂直列,方块漆成白色。在此网格上,我们将重复应用以下操作:
- 假设网格当前有 a 水平行和 b 垂直列。选择“垂直”或“水平”。
- 如果我们选择“垂直”,则在网格顶部插入一行,从而产生 (a+1) \times b 网格。
- 如果我们选择“水平”,则在网格的右端插入一列,从而产生 a \times (b+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
除了左下角的方块之外,三个方块中的任意两个都可以涂成黑色。
示例输入 2
2 1 3 4
示例输出 2
65
示例输入 3
31 41 59 265
示例输出 3
387222020