Дано множество $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 \ge 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$.

Подзадачи