Hide

# 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$ ($1 \le n \le 50$), $a$ ($1 \le a \le 50$), $b$ ($1 \le b \le 50$) and $c$ ($1 \le c \le 50$) 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 $10^9 + 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, c \le 10$ $2$ $1$ No additional constraints
Sample Input 1 Sample Output 1
5 1 2 3

1188

CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 2.5 - 3.9medium
Statistics Show