AT_abc003_4 [ABC003D] AtCoder社の冬

[problemUrl]: https://atcoder.jp/contests/abc003/tasks/abc003_4 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 $ 点が与えられる。 満点解法は非常に難しいので、部分点を確実に取ることから考えましょう。 ```

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 $ を満たさないため、部分点のテストケースに含まれることはありません。
- 無理に正解しようとせず、余裕のある人だけ挑戦してみてください。
                            

N/A

N/A