# [ROIR 2023 Day 2] 美丽序列

## 题目背景

翻译自 [ROIR 2023 D2T2](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day2.pdf)。

给定一个整数集合 $A$，其中的元素都在 $1$ 到 $8$ 之间。

一个由 $n$ 个在集合 $A$ 中的整数组成的序列 $[a_1, a_2, \dots , a_n]$，如果对于任意数字 $x$，序列中等于 $x$ 的所有元素彼此之间的距离不小于 $x$，则称这个序列是美丽的。换句话说，如果对于任意数字 $x$ 和任意的 $1 \le i < j \le n$，只要 $a_i = a_j = x$，则不等式 $j - i \ge x$ 必然成立，那么这样的序列 $a$ 就被称为美丽的序列。

例如，当 $A=\{1,2,3,4,5\}$ 时，序列 $[2,3,2,4,3,1,1,4]$ 是美丽的，而 $[1,1,4,5,1,4]$ 不是美丽的，因为这个序列中的两个 $4$ 之间的距离是 $3$。

## 题目描述

给定数字 $n$ 和集合 $A$，求出符合条件的美丽的序列的个数，对 $10^9 + 7$ 取模。

## 输入格式

输入的第一行包含两个整数 $n$ 和 $m$，分别表示序列的长度和集合 $A$ 的元素个数。

输入的第二行按升序给出了 $m$ 个互不相同的小于等于 $8$ 的正整数，表示集合 $A$ 的元素。

## 输出格式

输出一个整数，表示美丽序列的数量除以 $10^9 + 7$ 的余数。

## 样例 #1

### 样例输入 #1

```
3 2
1 2
```

### 样例输出 #1

```
5
```

## 提示

在样例中，美丽的序列有 $[1, 1, 1],[1, 1, 2],[1, 2, 1],[2, 1, 1],[2, 1, 2]$。序列 $[2, 2, 2],[1, 2, 2],[2, 2, 1]$ 不是美丽的，因为这三个序列中都有两个数值为 $2$ 的元素相距为 $1$。

本题使用捆绑测试。

| 子任务编号 | 分值 | 特殊性质 |
| :----------: | :----------: | :----------: |
| $1$ | $20$ | $A=\{1,2\},n\le10$ |
| $2$ | $17$ | $A=\{1,2\},n\le30$ |
| $3$ | $12$ | $A=\{1,2\}$ |
| $4$ | $6$ | $A=\{1,k\}$（$2\le k\le8$） |
| $5$ | $16$ | $A$ 中没有超过 $5$ 的元素 |
| $6$ | $15$ | 无特殊性质 |

对于 $100\%$ 的数据，$1 \le n \le 100,1 \le m \le 8$。