「FAOI-R2」A trip to Macao

赌场贴出了如下规则（**你可以忽略没有加粗的内容**）： 1. 所有玩家在注册后方可进行游戏。 2. 活动期间，**新注册的玩家可从抽奖盒内拿走一枚筹码。抽奖盒内共 $m$ 种筹码，面值分别为 $a_1,a_2,\ldots,a_m$ 澳元（均为正整数）**，每种一个，保证公平。 3. 本赌场仅提供一种游戏：猜拳。游戏开始时，双方各下注相同数量（以 $1$ 澳元为单位）的筹码；若猜拳分出胜负，则胜者拿走所有下注。 4. 根据上一条可知，**玩家一次游戏中赢得的筹码（正整数）不得超过自身所携带的筹码**。 5. 公平游戏，严禁作弊，违者严惩。 xhabc66 注册后，**连赢数局（可以是 $0$ 局，但没有输过，也没有平局过）**，最终带着 $n$ 澳元走出了赌场。 出赌场后，xhabc66 突然好奇他是怎么赢到这么多钱的。然而，他不记得他每局下了多少注，不记得他一共玩了多少局，甚至不记得他开始时拿走的筹码是什么面值。 **他想知道：他有多少种不同的赢钱方法。** **答案对 $10^9+7$ 取模。** > 两种赢钱方法在满足以下任何一个条件时，xhabc66 都会认为它们不同： > > - 他某一局的下注金额不同； > - 他玩的局数不同； > - 他开始时拿走的筹码的面值不同。 ### 形式化题意 求有多少个数列 $\{b_k\}$ 满足： 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$。 数列的长度 $k$ 可以是任何**正整数**。 答案对 $10^9+7$ 取模。 ## Input 两行。 第一行，两个正整数，$n,m$。 第二行，$m$ 个**从小到大排列**的正整数，$a_1 \sim a_m$。 ## Output 一行一个正整数，表示答案。 [samples] ## Background ## 本题目背景仅供引出题意，无任何不良诱导。 ## 出题人特别提醒：请勿在赌博非法地区模仿题目中的行为 这天，xhabc66 来到澳门旅游。一下飞机，他直奔赌场。 可是，今天的赌场格外热闹，不知发生了什么。 xhabc66 打开手机一看：啊，原来今天是 $12$ 月 $20$ 日！ 因此，赌场在做活动！一年一度！机不可失！ xhabc66 径直走进了赌场。 ## Note 样例 $1$ 解释： ```plain 1 2 3 4 1 2 4 2 3 4 2 4 3 4 4 ``` 样例 $2$ 解释： ```plain 1 2 3 4 5 1 2 3 5 1 2 4 5 ``` ---------- **本题采用捆绑测试。** | Subtask 编号 | $m \le$ | $n \le$ | 分值 | | :-: | :-: | :-: | :-: | | $0$ | $3$ | $3$ | $20$ | | $1$ | $10^5$ | $10^5$ | $40$ | | $2$ | $10^6$ | $10^8$ | $40$ | 对于 $100\%$ 的数据，$1 \le m \le 10^6$，$1 \le a_1<a_2<\ldots<a_m \le n \le 10^8$，$m \le n$。 > **提示：** 请注意本题不同寻常的内存限制！