Learning Arrangement

During the summer vacation, there are \(n\) days. MLE has listed \(m\) algorithms to choose from. On each day, he must study exactly one algorithm. However, studying the same algorithm for too many consecutive days causes boredom. For each algorithm \(i\), it can be learned consecutively for at most \(a_i\) days. Note that MLE does not have to study every algorithm. Two study arrangements are considered different if there is at least one day on which a different algorithm is studied.

Calculate the number of valid study arrangements over the \(n\) days, and output the answer modulo \(10^9+7\).

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of days and the number of algorithms available, respectively.

The second line contains \(m\) integers \(a_1,a_2,\dots,a_m\) where \(a_i\) denotes the maximum number of consecutive days algorithm \(i\) can be studied.

outputFormat

Output a single integer, the number of valid study arrangements modulo \(10^9+7\).

sample

1 2
1 1

2