P10099 [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$，求出长度为 $n$ 的符合要求的美丽的序列的个数，对 $10^9 + 7$ 取模。

输入的第一行包含两个整数 $n$ 和 $m$，分别表示序列的长度和集合 $A$ 的元素个数。 输入的第二行按升序给出了 $m$ 个互不相同的小于等于 $8$ 的正整数，表示集合 $A$ 的元素。

输出一个整数，表示美丽序列的数量除以 $10^9 + 7$ 的余数。

在样例中，美丽的序列有 $[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$。