Problem Description

Indeed Corporation decided to conduct a survey on job hunting activities for three companies: Su, Nu, and Ke.
They surveyed $X$ job seekers about their preferences for employment at Su, Nu, and Ke, and created a table summarizing whether each job seeker wants to work at each of the three companies.
(Such a table can be considered in $2^{3X}$ ways.)
Su, Nu, and Ke can each accept a maximum of $S$, $N$, and $K$ people, respectively.
Among the $2^{3X}$ possible tables, how many allow all job seekers to work at their desired companies?
Find the value modulo $1{,}000{,}000{,}007$.

Input Format

The input is given in the following format:

$ X $ $ S $ $ N $ $ K $

• The first line contains four integers $X$, $S$, $N$, and $K$ ($1 \leq S, N, K \leq X \leq 150$) separated by spaces.

Output Format

Output the desired value in one line.

Sample Input and Output

Sample Input #1

1 1 1 1

Sample Output #1

7

Sample Input #2

2 2 1 2

Sample Output #2

48

Sample Input #3

5 4 3 2

Sample Output #3

16384

Sample Input #4

15 12 9 6

Sample Output #4

667797496

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $1 \leq S, N, K \leq X \leq 12$, you will be awarded 25 points.
• If you solve all test cases, you will be awarded an additional 75 points.

Sample Explanation 1

Since there is one job seeker, there are 8 possible job preference tables. Among these, the case where the job seeker does not want to work at any company is considered as not being able to work at the desired company. Therefore, there are a total of 7 possible tables.

见题面 Input 部分

见题面 Output 部分