Hide

Problem B
Varied Amusements

Marika and Lisa love going to amusement parks. This time, they have their eyes set on a park with lots of exciting rides of three different types: tilt-a-whirls, roller coasters and drop towers. There are a different tilt-a-whirls, b roller coasters and c drop towers. They want to ride n rides in sequence, but never two rides of the same type in a row. In how many ways can they choose such sequences of n rides?

Input

The first and only line of input contains the integers n (1n50), a (1a50), b (1b50) and c (1c50) as described in the problem statement.

Output

Output the number of valid amusement ride sequences. Since this number can be very large, output it modulo 109+7.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group.

Group

Points

Constraints

1

1

n,a,b,c10

2

1

No additional constraints

Sample Input 1 Sample Output 1
5 1 2 3
1188
Hide

Please log in to submit a solution to this problem

Log in