← 返回题目列表

AtCoder · abc003_4

D. AtCoder的冬天

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

問題文

AtCoder公司的员工室 R \times C(R 行 C 被划分为(列)的区块,每个区块要么有员工桌,要么有服务器机架,或者是空闲空间。
在Coder公司所在地区的冬天很冷,为了尽量节省取暖费,他们决定只划分并使用员工室中必要的空间。
但是,由于材料问题,只能以平行于区块的长方形区域进行划分。
因此,
  • 在有员工桌或服务器机架的最上行的正上方,
  • 在有员工桌或服务器机架的最下行的正下方,
  • 在有员工桌或服务器机架的最左列的正左方,
  • 在桌子旁,或者在有服务器机架的最右列的正右侧
的 4 边围成的区域用墙围起来了。
这样被墙围住的区域 X \times Y(X 行 Y 变成了列)的区域。
另外,在AtCoder公司的员工室里,D 有个桌子,L 有个服务器机架。
起初,员工室里桌子和服务器机架是如何配置的,请写一个程序计算可能的排列数量对 1000000007 = 10^9+7 取模的余数。

入力

输入将以以下形式通过标准输入给出。
R C
X Y
D L
  1. 1 第n行给出AtCoder公司员工室的区块行数和列数的整数 R,\ C\ (1 ≦ R, C ≦ 30) 以空格分隔。
  2. 2 行表示社员室被墙壁围起部分的区块的行数和列数的整数 X,\ Y\ (1 ≦ X ≦ R,\ 1 ≦ Y ≦ C) 以空格分隔。
  3. 3 行表示社员室中社员桌的数量以及服务器机架的数量的整数 D,\ L\ (D, L ≧ 0,\ 1 ≦ D+L ≦ X \times Y) 以空格分隔。

出力

输出社员室中桌子和服务器机架可能的摆放模式数对 1000000007 = 10^9+7 取模之后的余数 1 行输出。
同时,输出末尾要加换行。

部分点

D+L = X \times Y 如果在测试情况下全部正确101 分满分中 100 分被给予。
满分解法非常困难,所以先考虑如何确实获得部分分数。

入力例 1

3 2
2 2
2 2

出力例 1

12
  • 这个情况是 D+L=X \times Y ,因此它可以包含在部分点测试用例中。
  • 下面 12 可能的布局是:这里D是一张桌子,L是一个服务器机架,.没有任何意义。
DD  DL  DL  LD  LD  LL  ..  ..  ..  ..  ..  ..
LL  DL  LD  DL  LD  DD  DD  DL  DL  LD  LD  LL
..  ..  ..  ..  ..  ..  LL  DL  LD  DL  LD  DD

入力例 2

4 5
3 1
3 0

出力例 2

10
  • 这个情况是 D+L=X \times Y ,因此它可以包含在部分点测试用例中。

入力例 3

23 18
15 13
100 95

出力例 3

364527243
  • 这个情况是 D+L=X \times Y ,因此它可以包含在部分点测试用例中。
  • 员工房间布局格局为 145180660592914517790287604376765671109248284280228061640640 这个在街上 除以 10^9+7 所得的余数 请输出 364527243 。 由于它不满足

入力例 4

30 30
24 22
145 132

出力例 4

976668549
  • 这个情况是 D+L=X \times Y ,因此不会包含在部分分数测试用例中。
  • 不要试图强迫自己得到正确的答案,只有在负担得起的情况下才尝试。