Christmas Tree

Time limit2sMemory limit128 MB

Summary

Count the ways to decorate an N-level tree where level k needs k ornaments split evenly among chosen colors, given limited red, green and blue ornaments.

Level: Medium6 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

Min-sik wants to decorate a Christmas tree made of N levels. The levels are numbered 1, 2, ..., N from top to bottom, and level k must contain exactly k ornaments.

Each ornament is red, green, or blue. For any level, once the colors used on that level are chosen, each chosen color must appear the same number of times. For example, placing 2 red ornaments and 1 blue ornament on level 3 is invalid because the two chosen colors have different counts. Placing 2 red ornaments and 2 blue ornaments on level 4 is valid.

Different color arrangements within the same level count as different decorations. Given the tree size and the available number of ornaments of each color, compute the number of different ways to decorate the tree.

Input

The first line contains the tree size N, the number of red ornaments R, the number of green ornaments G, and the number of blue ornaments B.

N is at most 10. Each of R, G, and B is between 0 and 100, inclusive.

Output

Print the number of ways to decorate the tree. If the tree cannot be decorated with the given ornaments, print 0.

The answer is at most 2^63 - 1.

Examples5

Example 1
Input
```
2 1 1 1
```
Expected output
```
6
```
Example 2
Input
```
2 2 1 0
```
Expected output
```
3
```
Example 3
Input
```
3 2 2 1
```
Expected output
```
0
```
Example 4
Input
```
3 2 2 2
```
Expected output
```
36
```
Example 5
Input
```
8 1 15 20
```
Expected output
```
197121
```