500. Dice Sequence Count

0

Hard

Vatsal is playing a dice game where he rolls a dice and generates a random number from 1 to 6 for each roll. However, there is a constraint introduced where Vatsal cannot roll the number i more than rollMax[i] (1-indexed) consecutive times.
Given an array of integers rollMax and an integer n, you need to determine the number of distinct sequences that can be obtained with exactly n rolls.
Two sequences are considered different if at least one element differs from each other.
Please note that the answer may be very large, so return it modulo 10^9 + 7.

Input Format

The first line of input contains the number of rolls, n.
The second line of input contains an array of integers from 1 to 6, representing the maximum roll limit for each number.

Output Format

Print the number of distinct sequences that can be obtained with exactly n rolls.

Example

Input

2
1 1 2 2 2 3

Output

34

Constraints

1 <= n <= 5000

rollMax.length == 6

1 <= rollMax[i] <= 15

rollMax.length == 6

1 <= rollMax[i] <= 15

Loading...

View Submissions

Console