Problem Description

The background of this problem is only used to introduce the story, and has no bad guidance.

The problem setter specially reminds: please do not imitate the behaviors in this problem in places where gambling is illegal.

One day, xhabc66 traveled to Macao. As soon as he got off the plane, he went straight to the casino.

However, the casino was unusually crowded today. Nobody knew what happened.

xhabc66 opened his phone and took a look: ah, it turned out that today was December $20$!

So, the casino was holding an event! Once a year! A chance you cannot miss!

xhabc66 walked straight into the casino.

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

1. All players can play only after registration.
2. During the event, newly registered players can take one chip from the lottery box. There are $m$ types of chips in the box, with values $a_1,a_2,\ldots,a_m$ Australian dollars (all positive integers), one of each, to ensure fairness.
3. This casino provides only one game: Rock-Paper-Scissors. At the start of the game, both sides bet the same amount of chips (in units of $1$ Australian dollar); if the game has a winner, the winner takes all the chips bet.
4. From the previous rule, the chips (a positive integer) a player wins in a single game must not exceed the chips they are carrying.
5. Fair play. Cheating is strictly forbidden. Violators will be punished severely.

After registering, xhabc66 won several games in a row (possibly $0$ games, but he never lost and never tied), and finally walked out of the casino with $n$ Australian dollars.

After leaving, xhabc66 suddenly became curious about how he won so much money. However, he does not remember how much he bet each round, how many rounds he played in total, or even the value of the chip he took at the beginning.

He wants to know: how many different ways does he have to win money.

Output the answer modulo $10^9+7$.

xhabc66 considers two winning ways different if any of the following holds:

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

Formal 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 $k$ can be any positive integer.

Output the answer modulo $10^9+7$.

Input Format

Two lines.

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

The second line contains $m$ positive integers $a_1 \sim a_m$ in increasing order.

Output Format

One line with one positive integer, the answer.

4 4
1 2 3 4

6

5 1
1

3

12345678 9
1 2 3 45 67 89 123 456 789

998899106

Hint

Explanation for Sample $1$:

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

Explanation for Sample $2$:

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

This problem uses bundled testdata.

For all 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 note the unusual memory limit of this problem.

Translated by ChatGPT 5