Description

There are $n$ days in the summer vacation. We assume MLE has enough time every day to study OI. MLE listed $m$ algorithms to choose from. Each day, MLE can only and must study exactly one algorithm.

Also, if MLE studies the same algorithm for a long time, they will get bored, so each algorithm cannot be studied for too many consecutive days. The $i$-th algorithm can be studied for at most $a_i$ consecutive days. MLE does not need to study all algorithms.

MLE wants to know how many different study schedules there are to spend these $n$ days. Two schedules are different if and only if there exists at least one day on which the studied algorithm is different. Since the number of schedules may be very large, you only need to output the number of schedules modulo $10^9+7$.

Input Format

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

Output Format

Output one line with one integer: the number of schedules modulo $10^9+7$.

3 2
1 2

4

2 1
1

0

8 5
4 2 3 4 2

356314

Hint

Sample Explanation

Sample #1

The first algorithm can be studied for at most one consecutive day, and the second one for at most two consecutive days. Therefore, there are four study schedules in total:

• $1,2,2$.
• $2,1,2$.
• $2,2,1$.
• $1,2,1$.

Sample #2

Since the only algorithm can be studied for at most one consecutive day, there is no valid schedule to spend $2$ days.

Constraints

This problem uses bundled testdata. Unless otherwise specified, the memory limit for each test point is 256MB.

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

Translated by ChatGPT 5