D - AtCoder社の冬 Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

AtCoder社の社員室は R \times C（R 行 C 列）の区画に区切られており、各区画には、社員のデスク、サーバーラックのどちらかがあるか、何もない空きスペースのどれかです。
AtCoder社のある地域の冬は寒く、暖房代をできるだけ節約するため、社員室の必要なスペースのみを区切って使用することに決めました。
しかし、資材の問題で、区画に平行な長方形の領域で区切らなければいけません。
そこで、
  • デスク、または、サーバーラックのある最も上の行のすぐ上、
  • デスク、または、サーバーラックのある最も下の行のすぐ下、
  • デスク、または、サーバーラックのある最も左の列のすぐ左、
  • デスク、または、サーバーラックのある最も右の列のすぐ右
の 4 辺で囲まれた区画を壁で囲みました。
すると壁で囲まれた領域は X \times Y（X 行 Y 列）の区画になりました。
また、AtCoder社の社員室には、D 個のデスクと、L 個のサーバーラックがあります。
もともと、社員室に、どのようにデスクとサーバーラックの配置されていたのか、考えうるパターン数を 1000000007 = 10^9+7 で割った余りを求めるプログラムを書いてください。

入力

入力は以下の形式で標準入力から与えられる。 
R C
X Y
D L
  1. 1 行目には、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 を満たさないため、部分点のテストケースに含まれることはありません。
  • 無理に正解しようとせず、余裕のある人だけ挑戦してみてください。