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 \leq N \leq 5000$
• $0 \leq 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.

3 1 2 0

2

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

600 100 200 300

522158867