ntopia

Time limit2sMemory limit512 MB

Summary

Count the number of ways to assign 1, 2, or 3 of three singers to each of S songs so each singer reaches a given song count.

Level: Medium7 of 10
Topics: Combinatorics, Math
Solved: No attempts yet

Problem

dotorya, kesakiyo, and hongjun7 teach at an algorithm camp, and the three of them formed an idol group named ntopia.

The debut album of ntopia holds $S$ songs. Every song must be sung by at least one of the three. Two of them may sing a song together, and all three may sing one together.

Given the number of songs each of the three has to record, write a program that counts the ways to make the album.

Album $A$ and album $B$ are different albums if there is at least one song whose singers differ between them.

Input

The first line contains the number of songs on the album, $S$ , followed by the number of songs that dotorya, kesakiyo, and hongjun7 each have to sing, separated by spaces. ( $1 \le S \le 10^6$ , and each of the three song counts is between $1$ and $S$ .)

Output

Print on the first line the number of ways to make the album, modulo 1,000,000,007.

Examples5

Example 1
Input
```
3 1 1 1
```
Expected output
```
6
```
Example 2
Input
```
3 3 1 1
```
Expected output
```
9
```
Example 3
Input
```
50 10 10 10
```
Expected output
```
0
```
Example 4
Input
```
18 12 8 9
```
Expected output
```
81451692
```
Example 5
Input
```
50 25 25 25
```
Expected output
```
198591037
```