123 Pairs

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.

Examples

Input

3 1 2 0

Output

2

Input

600 100 200 300

Output

522158867

inputFormat

Input

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

N A B C

outputFormat

Output

Print the answer.

Examples

Input

3 1 2 0

Output

2

Input

600 100 200 300

Output

522158867

样例

3 1 2 0

2