28413번 - Красивые последовательности 서브태스크다국어

Дано множество $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$ друг от друга.