ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1962. В китайском ресторане

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Когда Вова приехал в Гуанчжоу, его китайские друзья первым делом пригласили его в ресторан. Всего в ресторан пришло n человек, включая Вову. Официант предложил разместиться всей компании за традиционным большим круглым столом с вращающейся подставкой для блюд в центре.
Вову, как гостя, сразу усадили на почётное место около двери. После чего m человек из присутствующих заявили, что непременно хотят сидеть рядом с определённым человеком. Требуется определить количество допустимых рассадок друзей Вовы за столом.

Исходные данные

В первой строке записаны целые числа n и m (2 ≤ n ≤ 100; 0 ≤ mn). В следующих m строках записаны целые числа k1, …, km, где ki — номер человека, рядом с которым изъявил желание сидеть человек с номером i (1 ≤ kin; kii). Вова, как почётный гость, имеет номер 1. А его друзья пронумерованы целыми числами от 2 до n.

Результат

Выведите количество допустимых вариантов рассадки, взятое по модулю 109 + 7.

Примеры

исходные данныерезультат
6 6
2
1
1
5
6
5
4
4 3
2
3
1
0
Источник задачи: Открытое личное первенство УрФУ по программированию 2013