Background

Translated from ROIR 2023 D2T2。

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

Problem Description

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

Input Format

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 Format

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

3 2
1 2

5

Hint

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.

Constraints: for $100\%$ of the testdata, $1 \le n \le 100,1 \le m \le 8$。

Translated by ChatGPT 5