Dhoni has 3 types of water bottles. He has exactly $a$ bottles of volume 0.5 liters, $b$ bottles of volume 1 liter, and $c$ bottles of volume 2 liters. Your task is to help Dhoni count the number of ways to carry exactly $n$ liters of water. Two variants are different from each other only if they differ in the number of bottles of at least one kind.

Input

The first line will contain four integers — $n, a, b, c (1 \leq n \leq 30000, 0 \leq a, b, c \leq 10000)$.

Output

Print one number — the solution to the problem. If it is not possible to make exactly $n$ liters of water, print $0$.

Samples

Input	Output
10 5 5 5	9

Input	Output
3 0 0 2	0