← 返回题目列表

AtCoder · agc046_b

B. 扩展

中文机器翻译题面 查看原题

分数: 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