Красивые последовательности

Дано множество $A$, элементами которого являются различные целые числа от $1$ до $8$.

Рассмотрим последовательность $\[a\_1, a\_2, \dots , a\_n]$ из $n$ целых чисел, каждое из которых выбрано из множества $A$. Будем называть эту последовательность красивой, если для любого числа $x$ все элементы последовательности, равные $x$, находятся на расстоянии не меньше $x$ друг от друга. Иначе говоря, для любого числа x и для любых двух индексов $1 \le i < j \le n$, таких, что $a\_i = a\_j = x$, должно выполняться неравенство $j - i > x$.

Требуется посчитать количество красивых последовательностей для заданного числа $n$ и множества $A$, и вывести остаток от деления этого количества на число $10^9 + 7$.

В первой строке ввода даны два целых числа $n$ и $m$ — длина последовательности и количество элементов множества $A$ ($1 \le n \le 100$, $1 \le m \le 8$).

Во второй строке ввода даны $m$ различных целых чисел $a\_i$ в порядке возрастания — элементы множества $A$ ($1 \le a\_i \le 8$, $a\_i < a\_{i+1}$).

Выведите одно целое число — остаток от деления количества красивых последовательностей на число $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$ друг от друга.