D - Hanjo Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

H メートル、横 W メートルの長方形の部屋があります。
この部屋に 2 メートル × 1 メートルの区別できない畳 (長方形のタイル) A 枚と、1 メートル × 1 メートルの区別できない半畳 (正方形のタイル) B 枚を敷き詰めます。 2 メートル × 1 メートルの畳は縦長にも横長にも使うことができます。
敷き詰める方法は何通りあるでしょうか?
なお、2A + B = HW であることが保証されます。 また、回転や反転を行うことで初めて一致するような敷き詰め方は区別します。

制約

  • 入力は全て整数
  • 1 ≤ H, W
  • HW ≤ 16
  • 0 ≤ A, B
  • 2A + B = HW

入力

入力は以下の形式で標準入力から与えられる。

H W A B

出力

答えを出力せよ。


入力例 1

2 2 1 2

出力例 1

4

以下の 4 つです。


入力例 2

3 3 4 1

出力例 2

18

以下の 6 つと、これらを回転させたものが含まれます。


入力例 3

4 4 8 0

出力例 3

36

Score : 400 points

Problem Statement

We have a rectangular room that is H meters long and W meters wide.
We will cover this room with A indistinguishable 2 meters \times 1 meters rectangular tatami mats and B indistinguishable 1 meter \times 1 meter square tatami mats. The rectangular mats can be used in either direction: they can be 2 meters long and 1 meter wide, or 1 meter long and 2 meters wide.
How many ways are there to do this?
Here, it is guaranteed that 2A + B = HW, and two ways are distinguished if they match only after rotation, reflection, or both.

Constraints

  • All values in input are integers.
  • 1 ≤ H, W
  • HW ≤ 16
  • 0 ≤ A, B
  • 2A + B = HW

Input

Input is given from Standard Input in the following format:

H W A B

Output

Print the answer.


Sample Input 1

2 2 1 2

Sample Output 1

4

There are four ways as follows:


Sample Input 2

3 3 4 1

Sample Output 2

18

There are six ways as follows, and their rotations.


Sample Input 3

4 4 8 0

Sample Output 3

36