R \times C

R

C

• デスク、または、サーバーラックのある最も上の行のすぐ上、
• デスク、または、サーバーラックのある最も下の行のすぐ下、
• デスク、または、サーバーラックのある最も左の列のすぐ左、
• デスク、または、サーバーラックのある最も右の列のすぐ右

4

X \times Y

X

Y

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

3 2
2 2
2 2

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

4 5
3 1
3 0

10

• このケースは $D+L=X \times Y$ を満たすため、部分点のテストケースに含まれる可能性があります。

23 18
15 13
100 95

364527243

• このケースは $D+L=X \times Y$ を満たすため、部分点のテストケースに含まれる可能性があります。
• 社員室の配置パターンは $145180660592914517790287604376765671109248284280228061640640$ 通りで、これを $10^9+7$ で割った余りである $364527243$ を出力してください。

30 30
24 22
145 132

976668549

• このケースは $D+L=X \times Y$ を満たさないため、部分点のテストケースに含まれることはありません。
• 無理に正解しようとせず、余裕のある人だけ挑戦してみてください。