版权声明

本题版权归 所有。

题目来源：https://www.luogu.com.cn/problem/P10036

注意

本题的空间限制为 8 MB。

题目描述

求有多少个数列 $\{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

数据范围

本题采用捆绑测试。

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