题目背景

这天，xhabc66 来到澳门旅游。一下飞机，他直奔赌场。

可是，今天的赌场格外热闹，不知发生了什么。

xhabc66 打开手机一看：啊，原来今天是 $12$ 月 $20$ 日！

因此，赌场在做活动！一年一度！机不可失！

xhabc66 径直走进了赌场。

题目描述

赌场贴出了如下规则（你可以忽略没有加粗的内容）：

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$ 取模。

输入格式

两行。

第一行，两个正整数，$n,m$。

第二行，$m$ 个从小到大排列的正整数，$a_1 \sim a_m$。

输出格式

一行一个正整数，表示答案。

4 4
1 2 3 4

6

5 1
1

3

12345678 9
1 2 3 45 67 89 123 456 789

998899106

提示

样例 $1$ 解释：

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

样例 $2$ 解释：

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

---

本题采用捆绑测试。

Subtask 编号	$m \le$	$n \le$	分值
$0$	$3$		$20$
$1$	$10^5$		$40$
$2$	$10^6$	$10^8$

对于 $100\%$ 的数据，$1 \le m \le 10^6$，$1 \le a_1<a_2<\ldots<a_m \le n \le 10^8$，$m \le n$。

提示： 请注意本题不同寻常的内存限制！