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

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

Рассмотрим последовательность [a₁, a₂, ..., a_n] из n целых чисел, каждое из которых выбрано из множества A. Будем называть эту последовательность красивой, если для любого числа x все элементы последовательности, равные x, находятся на расстоянии не меньше x друг от друга. Иначе говоря, для любого числа x и для любых двух индексов 1 ≤ i < j ≤ n, таких, что a_i = a_j = x, должно выполняться неравенство j - i ≥ x.

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

Входные данные

В первой строке входного файла INPUT.TXT даны два целых числа n и m – длина последовательности и количество элементов множества A (1 ≤ n ≤ 100, 1 ≤ m ≤ 8).

Во второй строке ввода даны m различных целых чисел a_i в порядке возрастания – элементы множества A (1 ≤ a_i ≤ 8, a_i < a_i+1).

Выходные данные

В выходной файл OUTPUT.TXT выведите одно целое число – остаток от деления количества красивых последовательностей на число 10⁹+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 друг от друга.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!