题目背景

翻译自 ROIR 2023 D2T2。

给定一个整数集合 $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$ 的余数。

3 2
1 2

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

本题使用捆绑测试。

对于 $100\%$ 的数据，$1 \le n \le 100,1 \le m \le 8$。