7342: ABC235 —— G - Gardens
[Creator : ]
Description
Takahashi has A apple seedlings, B banana seedlings, and C cherry seedlings. Seedlings of the same kind cannot be distinguished.
He will plant these seedlings in his N gardens so that all of the following conditions are satisfied.
Two ways are distinguished when there is a garden with different sets of seedlings planted in these two ways.
He will plant these seedlings in his N gardens so that all of the following conditions are satisfied.
- At least one seedling must be planted in every garden.
- It is not allowed to plant two or more seedlings of the same kind in the same garden.
- It is not necessary to plant all seedlings he has.
Two ways are distinguished when there is a garden with different sets of seedlings planted in these two ways.
Input
Input is given from Standard Input in the following format:
$N\ A\ B\ C$
$N\ A\ B\ C$
Output
Print the answer.
Constraints
$1≤N≤5×10^6$
$0 \leq A \leq N$
$0 \leq B \leq N$
$0 \leq C \leq N$
All values in input are integers.
$0 \leq A \leq N$
$0 \leq B \leq N$
$0 \leq C \leq N$
All values in input are integers.
Sample 1 Input
2 2 1 1
Sample 1 Output
21
As illustrated below, there are 21 ways to plant seedlings to satisfy the conditions.
(The two frames arranged vertically are the gardens. A, B, C stand for apple, banana, cherry, respectively.)
Sample 2 Input
2 0 0 0
Sample 2 Output
0
There may be no way to plant seedlings to satisfy the conditions.
Sample 3 Input
2 0 2 2
Sample 3 Output
9
100 12 34 56
769445780
Sample 4 Input
5000000 2521993 2967363 3802088
Sample 4 Output
264705492