G. Cubes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Veronica loves to play with her toys. Cubes are one of her favorite toys.

Veronica builds towers, pyramids, and many other forms from multi-colored cubes. Today, Veronica wants to build a tower of $$$n$$$ cubes in height. Veronica has unlimited quantities of red, green, and blue cubes. Veronica wants to build a beautiful multi-colored tower, so she wants the tower to have no more than $$$k_r$$$ in a row of red cubes, $$$k_g$$$ in a row of green cubes, and $$$k_b$$$ in a row of blue cubes.

Help Veronica to determine how many different towers with a height of $$$n$$$ cubes she can build. Since this number may be very large, print the answer modulo $$$10^9 + 7$$$.

Input

A single line contains four integers $$$n$$$, $$$k_r$$$, $$$k_g$$$, $$$k_b$$$ $$$(1\leq n,k_r,k_g,k_b\leq 10^6)$$$  — tower height and restrictions on the number of consecutive red, green and blue cubes, respectively.

Output

In a single line, print an integer – the number of different variants of towers, taken modulo $$$10^9 + 7$$$.

Examples
Input
5 2 2 2
Output
180
Input
6 1 1 3
Output
222
Input
3 1 1 1
Output
12
Input
4 4 4 4
Output
81