Задача E. Рассадка пассажиров ≡

Условие

Илон Маск закончил создание транспорта будущего — Hyperloop. Hyperloop — расположенный на опорах надземный трубопровод, внутри которого с высокой скоростью в одном направлении перемещаются одиночные транспортные капсулы. Пассажирский вариант предполагает n рядов по одному сиденью. Однако из-за конструктивных недостатков люди не могут сидеть на двух подряд идущих рядах. Поэтому, когда продаётся билет с номером места a_i из продажи исчезает сам этот билет, и два соседних с ним билета.

Слон Пахом подрабатывает контролёром на Hyperloop. На рейс уже распродано k билетов с номерами a_i. Так как все хотят прокатиться на Hyperloop, вы точно знаете, что все билеты будут распроданы. После продажи k билетов вам стало интересно, сколько существует различных способов продажи оставшихся билетов так, чтобы не нарушить правила продажи билетов. Способы считаются различными, если в одном из них существует хотя бы один билет, не проданный в другом.

Формат входного файла

Первая строка входного файла содержит два целых числа N и K. Далее следует K строк содержащих по одному числу a_i. Гарантируется, что для всех пар i и j выполняется условие |a_i − a_j| ≥ 2 .

Формат выходного файла

Выходной файл должен содержать одно  — количество вариантов рассадки пассажиров по модулю 1000000007.

Ограничения

1 ≤ N ≤ 10⁶; 1 ≤ K ≤ 10⁵; 1 ≤ a_i ≤ N

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Примеры тестов

4 2
2
4

1

3 0

2

5 1
1

2