# 「FAOI-R2」A trip to Macao (B)

## 题目背景

这天，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$。

## 输出格式

一行一个正整数，表示答案。

## 样例 #1

### 样例输入 #1

```
4 4
1 2 3 4
```

### 样例输出 #1

```
6
```

## 样例 #2

### 样例输入 #2

```
5 1
1
```

### 样例输出 #2

```
3
```

## 样例 #3

### 样例输入 #3

```
12345678 9
1 2 3 45 67 89 123 456 789
```

### 样例输出 #3

```
998899106
```

## 提示

样例 $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$。

> **提示：** 请注意本题不同寻常的内存限制！