P10036 "FAOI-R2" A trip to Macao

## 本题目背景仅供引出题意，无任何不良诱导。 ## 出题人特别提醒：请勿在赌博非法地区模仿题目中的行为 这天，xhabc66 来到澳门旅游。一下飞机，他直奔赌场。 可是，今天的赌场格外热闹，不知发生了什么。 xhabc66 打开手机一看：啊，原来今天是 $12$ 月 $20$ 日！ 因此，赌场在做活动！一年一度！机不可失！ xhabc66 径直走进了赌场。

## 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$.

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**.

One line with one positive integer, the answer.

Explanation for Sample $1$: ```plain 1 2 3 4 1 2 4 2 3 4 2 4 3 4 4 ``` Explanation for Sample $2$: ```plain 1 2 3 4 5 1 2 3 5 1 2 4 5 ``` ---------- **This problem uses bundled testdata.** | Subtask ID | $m \le$ | $n \le$ | Score | | :-: | :-: | :-: | :-: | | $0$ | $3$ | $3$ | $20$ | | $1$ | $10^5$ | $10^5$ | $40$ | | $2$ | $10^6$ | $10^8$ | $40$ | For all data, $1 \le m \le 10^6$, $1 \le a_1