Problem Background

During the summer vacation, MLE decides to learn some OI algorithms.

Problem Description

The summer vacation lasts for \( n \) days, and we assume MLE has ample time to study OI each day. MLE has listed \( m \) algorithms to choose from. MLE can only and must study one algorithm per day.

Moreover, MLE gets bored studying the same algorithm for too long, so no algorithm can be studied consecutively for too many days. The \( i \)-th algorithm can be studied for a maximum of \( a_i \) consecutive days. MLE does not need to study all the algorithms.

MLE wants to know how many different study schedules he can follow to spend these \( n \) days. Two schedules are considered different if there is at least one day where a different algorithm is studied. Since the number of methods might be too large, you only need to output the number of plans modulo \( 10^9+7 \).

Input Format

The first line contains two integers \( n \) and \( m \).
The second line contains \( m \) integers \( a_1, a_2, \cdots, a_m \).

Output Format

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

Sample Input and Output

Sample Input #1

3 2
1 2

Sample Output #1

4

Sample Input #2

2 1
1

Sample Output #2

0

Sample Input #3

8 5
4 2 3 4 2

Sample Output #3

356314

Notes

Sample Explanation

Sample #1

The first algorithm can be studied for a maximum of one consecutive day, and the second for a maximum of two consecutive days. Hence, there are four possible study schedules:

• \( 1, 2, 2 \)
• \( 2, 1, 2 \)
• \( 2, 2, 1 \)
• \( 1, 2, 1 \)

Sample #2

Since the only algorithm can only be studied for a maximum of one consecutive day, there is no valid schedule to spend 2 days.

Data Range

This problem uses batched testing. Unless otherwise specified, the memory limit for each test case is 256MB.

For all data, \( 1 \le a_i \le n \le 7 \times 10^3 \), \( 1 \le m \le 7 \times 10^3 \).

见题面 Input 部分

见题面 Output 部分