Background

After finally solving classmate dm’s difficult problem, dm agreed to help contact “V-shen”. However, dm has a habit: when contacting classmates, he prefers to contact them in groups, and the grouping method is special — the number of people in the $i$-th group must be greater than a specified number $C_i$. While dm was contacting people, “V-shen” wondered how many grouping plans there could be under dm’s rules. He thought and thought, but still couldn’t figure it out. So he turned to you for help: can you compute how many grouping plans there are according to dm’s rules?

Problem Description

There are $N$ people in V-shen’s class. dm wants to split them into $M$ groups. The number of people in the $i$-th group must be greater than the given positive integer $C_i$. How many different plans are there? Two plans are considered the same if and only if, for every $i$, the sizes of the $i$-th group are equal in both plans. Since the answer can be large, output it modulo $10^9+7$.

Input Format

The first line contains two integers $N$ and $M$. The next $M$ lines each contain one integer, denoting $C_i$.

Output Format

Output a single line containing one integer — the number of plans modulo $10^9+7$.

10 3
1
2
3

3

Hint

Sample Explanation: There are three plans, with group sizes $(3, 3, 4)$, $(2, 4, 4)$, and $(2, 3, 5)$.

Constraints:

• For $30\%$ of the testdata, $N, M \le 10$.
• For $60\%$ of the testdata, $N, M \le 1000$.
• For $100\%$ of the testdata, $1 \le N, M \le 10^6$, $1 \le C_i \le 1000$.

The testdata guarantees that there is at least one valid plan.

Translated by ChatGPT 5