Problem Background

On this day, xhabc66 came to Macau for a trip. As soon as he got off the plane, he headed straight to the casino.

However, today's casino was unusually lively, and xhabc66 didn't know why.

He opened his phone and saw: Ah, it turns out that today is December 20th!

So, the casino is holding an event! A once-a-year opportunity! Don't miss it!

xhabc66 walked straight into the casino.

Problem Description

The casino posted the following rules (you can ignore the content that is not in bold):

1. All players must register before they can play the game.
2. During the event, newly registered players can take one chip from the lottery box. The lottery box contains $m$ types of chips, with face values of $a_1, a_2, \ldots, a_m$ Macau patacas (all positive integers), each type having one, ensuring fairness.
3. The casino only offers one game: rock-paper-scissors. At the start of the game, both parties bet the same amount (in units of 1 Macau pataca) of chips; if there is a winner in rock-paper-scissors, the winner takes all the bets.
4. According to the previous rule, the number of chips a player can win in one game (a positive integer) must not exceed the number of chips they carry.
5. Fair play is strictly enforced, and cheating is strictly prohibited, with severe penalties for violators.

After registering, xhabc66 won several rounds (it could be 0 rounds, but he never lost or had a draw), and eventually left the casino with $n$ Macau patacas.

After leaving the casino, xhabc66 suddenly wondered how he had won so much money. However, he didn't remember how much he had bet in each round, how many rounds he had played, or even what the face value of the chip he had taken at the beginning was.

He wants to know: how many different ways he could have won the money.

The answer should be taken modulo $10^9+7$.

Two ways of winning are considered different if any of the following conditions are met:

• The amount he bet in a certain round is different;
• The number of rounds he played is different;
• The face value of the chip he took at the beginning is different.

Formalized Problem Statement

Find how many sequences $\{b_k\}$ satisfy:

1. $\forall i \in [1, k], b_i \in \mathbb{N^*}$;
2. $\forall i \in [2, k], b_i \in [b_{i-1}+1, b_{i-1} \times 2]$;
3. $b_1 \in \{a_m\}$;
4. $b_k = n$.

The length of the sequence $k$ can be any positive integer.

The answer should be taken modulo $10^9+7$.

Input Format

Two lines.

The first line contains two positive integers, $n$ and $m$.

The second line contains $m$ sorted in ascending order positive integers, $a_1$ to $a_m$.

Output Format

One line containing a positive integer, representing the answer.

Sample Input and Output

Sample Input #1

4 4
1 2 3 4

Sample Output #1

6

Sample Input #2

5 1
1

Sample Output #2

3

Sample Input #3

12345678 9
1 2 3 45 67 89 123 456 789

Sample Output #3

998899106

Notes

Sample #1 Explanation

1 2 3 4
1 2 4
2 3 4
2 4
3 4
4

Sample #2 Explanation

1 2 3 4 5
1 2 3 5
1 2 4 5

This problem uses batched testing.

For $100\%$ of the data, $1 \le m \le 10^6$, $1 \le a_1 < a_2 < \ldots < a_m \le n \le 10^8$, and $m \le n$.

Hint: Please be aware of the unusual memory limit for this problem!

见题面 Input 部分

见题面 Output 部分