P10099 [ROIR 2023] Beautiful Sequence (Day 2)

Translated from [ROIR 2023 D2T2](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day2.pdf)。 You are given an integer set $A$, where all elements are between $1$ and $8$. A sequence $[a_1, a_2, \dots , a_n]$ of length $n$ consisting of integers from set $A$ is called beautiful if, for any number $x$, the distance between any two elements equal to $x$ in the sequence is at least $x$. In other words, for any number $x$ and any $1 \le i < j \le n$, if $a_i = a_j = x$, then the inequality $j - i \ge x$ must hold. Such a sequence $a$ is called a beautiful sequence. For example, when $A=\{1,2,3,4,5\}$, the sequence $[2,3,2,4,3,1,1,4]$ is beautiful, while $[1,1,4,5,1,4]$ is not beautiful, because the distance between the two $4$'s in this sequence is $3$.

Given the number $n$ and the set $A$, find the number of beautiful sequences of length $n$ that satisfy the requirement, modulo $10^9 + 7$.

The first line contains two integers $n$ and $m$, representing the length of the sequence and the number of elements in set $A$. The second line gives $m$ distinct positive integers in ascending order, each not exceeding $8$, representing the elements of set $A$.

Output one integer, the remainder of the number of beautiful sequences modulo $10^9 + 7$.

In the sample, the beautiful sequences are $[1, 1, 1],[1, 1, 2],[1, 2, 1],[2, 1, 1],[2, 1, 2]$. The sequences $[2, 2, 2],[1, 2, 2],[2, 2, 1]$ are not beautiful, because in each of these three sequences there are two elements with value $2$ whose distance is $1$. This problem uses bundled testdata. | Subtask ID | Score | Special Properties | | :----------: | :----------: | :----------: | | $1$ | $5$ | $A=\{1,2\},n\le10$ | | $2$ | $10$ | $A=\{1,2\},n\le30$ | | $3$ | $15$ | $A=\{1,2\}$ | | $4$ | $20$ | $A=\{1,k\}$（$2\le k\le8$） | | $5$ | $30$ | No element in $A$ is greater than $5$ | | $6$ | $20$ | No special properties | Constraints: for $100\%$ of the testdata, $1 \le n \le 100,1 \le m \le 8$。 Translated by ChatGPT 5