AT_abc003_4 [ABC003D] AtCoder社の冬

AtCoder 社的员工室被划分为 $R \times C$（$R$ 行 $C$ 列）的格子，每个格子中可能有员工的桌子、服务器机架，或者什么都没有的空格。 由于 AtCoder 所在地区的冬天很冷，为了尽量节省取暖费用，公司决定只使用员工室中必要的空间。 但由于材料的限制，必须用与格子平行的矩形区域来划分空间。 因此， - 在有桌子或服务器机架的最上面一行的正上方， - 在有桌子或服务器机架的最下面一行的正下方， - 在有桌子或服务器机架的最左边一列的正左方， - 在有桌子或服务器机架的最右边一列的正右方， 用墙围成一个矩形区域。 这样，被墙围住的区域就是 $X \times Y$（$X$ 行 $Y$ 列）的格子。 另外，AtCoder 社的员工室里有 $D$ 个桌子和 $L$ 个服务器机架。 请编写程序，计算员工室中桌子和服务器机架的所有可能的摆放方案数，并对 $1000000007 = 10^9+7$ 取模。 输入按以下格式从标准输入给出。 1. 第 $1$ 行给出员工室的行数和列数 $R,\ C\ (1 \leq R,\ C \leq 30)$，用空格分隔。 2. 第 $2$ 行给出被墙围住的区域的行数和列数 $X,\ Y\ (1 \leq X \leq R,\ 1 \leq Y \leq C)$，用空格分隔。 3. 第 $3$ 行给出员工室中桌子的数量和服务器机架的数量 $D,\ L\ (D,\ L \geq 0,\ 1 \leq D+L \leq X \times Y)$，用空格分隔。 请输出员工室中桌子和服务器机架的所有可能的摆放方案数，对 $1000000007 = 10^9+7$ 取模，并在输出末尾加上换行符。 如果 $D+L = X \times Y$ 的测试用例全部正确，可以获得 $101$ 分中的 $100$ 分。 满分解法非常困难，建议先考虑确保拿到部分分。

第 $1$ 行：两个整数 $R\ C$，表示员工室的行数和列数。 第 $2$ 行：两个整数 $X\ Y$，表示被墙围住的区域的行数和列数。 第 $3$ 行：两个整数 $D\ L$，表示桌子的数量和服务器机架的数量。

输出一个整数，表示所有可能的摆放方案数，对 $1000000007$ 取模，并以换行结束。

- $D+L = X \times Y$ 的情况属于部分分测试用例。 - 满分解法较难，建议先确保部分分。 - $1 \leq R, C \leq 30$ - $1 \leq X \leq R$ - $1 \leq Y \leq C$ - $D, L \geq 0$ - $1 \leq D+L \leq X \times Y$ 由 ChatGPT 4.1 翻译