Заключительный тур олимпиады

На финальный тур олимпиады прошло N участников, и всех их надо рассадить в две аудитории.
Умная нейросеть проанализировала социальные сети участников и выделила пары друзей. Организаторы, располагая этой информацией, хотят распределить участников между двумя аудиториями так, чтобы в них сидело равное количество участников и никакие два друга не сидели в одной аудитории.
Это довольно просто сделать, но организаторов очень волнует другой вопрос: сколько существует подходящих распределений участников по аудиториям. Два распределения считаются различными, если существует пара участников, которые сидят в одной и той же аудитории в одном распределении, но в разных аудиториях в другом распределении.
Например, по такой логике рассадки варианты (1, 2) / (3, 4) и (3, 4) / (1, 2) считаются одинаковыми.
Организаторы не могут ответить на этот вопрос сами, поэтому просят вашей помощи.

Формат входных данных
В первой строке входного файла записаны два целых числа N и M — количество участников и количество выявленных пар друзей соответственно.
Далее на M строках содержится по два различных числа ai и bi — номера участников i-й пары друзей.
Гарантируется, что каждая пара друзей записана ровно один раз.

Формат выходных данных
В выходной файл необходимо вывести только одно целое число — количество различных распределений участников по аудиториям такое, что любые два друга пишут олимпиаду в разных аудиториях, а в каждой из аудиторий сидит равное количество участников.
Так как число может получиться очень большим, то требуется вывести его по модулю 10^9 + 7.

Примеры

input.txt
6 3
1 2
2 3
4 5

output.txt
2

input.txt
5 0

output.txt
0

0

tetacol157, а тут что не получается?

0

Каков алгоритм будет тут?

0

tetacol157, а какие ты знаешь алгоритмы?

0