Acka

Count the ways to assign each of S songs to a nonempty subset of three singers so that the three singers get exactly D, K, and H songs.

Medium6CombinatoricsDynamic programmingMathNo attempts yetTime limit2sMemory limit512 MB

Description

Examples5

Problem

dotorya, kesakiyo, and hongjun7 teach at an algorithm camp. In room 301 they agreed to form the project idol group Acka.

Acka's debut album holds $S$ songs. Every song has to be sung by at least one of the three. A song may be sung by two of them, and it may be sung by all three.

Given how many songs each person has to record, write a program that counts the ways to make the album.

Two albums A and B are different if there is a song whose singers differ between them.

Input

The first line contains four integers $S$ , $D$ , $K$ , $H$ , separated by spaces. $S$ is the number of songs on the album, and $D$ , $K$ , $H$ are the numbers of songs that dotorya, kesakiyo, and hongjun7 have to sing.

$1 \le S \le 50$ , $1 \le D, K, H \le S$

Output

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