SolveMe

Time limit8sMemory limit512 MB

Summary

Count pairs of maps A and B on N rooms where following A X times, then B, A Y times, B, and A Z times returns every room to its start, modulo 1,000,000,007.

Level: Hard9 of 10
Topics: Combinatorics, Math, Number theory
Solved: No attempts yet

Problem

There are $N$ rooms, and each room's floor has a picture of a rabbit. If you stand on the right ear of the rabbit picture in room $r$ , you teleport onto the tail of the rabbit drawn in room $A[r]$ . Likewise, standing on the left ear of the rabbit picture in room $r$ teleports you onto the tail of the rabbit drawn in room $B[r]$ .

You are given integers $X$ , $Y$ , and $Z$ . The cat wants to set the teleports so that the following condition holds. Among the $N^{2N}$ ways to set the teleports, count how many satisfy the condition, modulo 1,000,000,007.

Condition: For every room $r$ , starting from $r$ , if you step on the right ear exactly $X$ times, the left ear exactly once, the right ear exactly $Y$ times, the left ear exactly once, and the right ear exactly $Z$ times, you return to $r$ .

Input

The input is given in the following format:

$N$ $X$ $Y$ $Z$

Output

Print the number of teleport settings that satisfy the condition, modulo 1,000,000,007, on a single line.

Constraints

$N$ is between 1 and 1,000, inclusive.
$X$ , $Y$ , and $Z$ are between 0 and 1,000,000,000,000,000,000, inclusive.

Examples2

Example 1
Input
```
3 1 0 1
```
Expected output
```
18
```
Example 2
Input
```
5 8 5 8
```
Expected output
```
120
```