J - 123 Pairs Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1500 点

問題文

1 以上 2N　以下の整数を考えます。 すぬけ君は、これらの整数を以下の条件を満たすように N 組のペアに分けたいです:

  • 1 以上 2N 以下の整数はそれぞれちょうど一つのペアに含まれる。
  • 差が 1 であるようなペアがちょうど A 組ある。
  • 差が 2 であるようなペアがちょうど B 組ある。
  • 差が 3 であるようなペアがちょうど C 組ある。

制約により N = A + B + C　であることが保証されているので、差が 4 以上のペアは存在しません。

このようにペアに分ける方法が何通りあるか、modulo 10^9+7　で求めてください。

制約

  • 1 ≤ N ≤ 5000
  • 0 ≤ A, B, C
  • A + B + C = N

入力

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

N A B C

出力

答えを出力せよ。

入力例 1

3 1 2 0

出力例 1

2

1-2, 3-5, 4-6 と 1-3, 2-4, 5-6 の二通りの方法があります。

入力例 2

600 100 200 300

出力例 2

522158867

Score : 1500 points

Problem Statement

Consider all integers between 1 and 2N, inclusive. Snuke wants to divide these integers into N pairs such that:

  • Each integer between 1 and 2N is contained in exactly one of the pairs.
  • In exactly A pairs, the difference between the two integers is 1.
  • In exactly B pairs, the difference between the two integers is 2.
  • In exactly C pairs, the difference between the two integers is 3.

Note that the constraints guarantee that N = A + B + C, thus no pair can have the difference of 4 or more.

Compute the number of ways to do this, modulo 10^9+7.

Constraints

  • 1 ≤ N ≤ 5000
  • 0 ≤ A, B, C
  • A + B + C = N

Input

The input is given from Standard Input in the following format:

N A B C

Output

Print the answer.

Sample Input 1

3 1 2 0

Sample Output 1

2

There are two possibilities: 1-2, 3-5, 4-6 or 1-3, 2-4, 5-6.

Sample Input 2

600 100 200 300

Sample Output 2

522158867