Алекс распределяет n наблюдателей по двум сменам: утренней и вечерней. Каждый человек должен попасть ровно в одну смену; пустая смена допускается.
Для некоторых пар наблюдателей известно, что они должны работать в разных сменах, поскольку пользуются одним комплектом оборудования. Других ограничений нет.
Посчитайте количество допустимых распределений по модулю 1 000 000 007. Смены различаются: поменять у всех людей утро на вечер означает другое распределение. Если выполнить все ограничения невозможно, выведите 0.
Входные данные
Первая строка содержит целые числа n и m (1 ≤ n ≤ 200 000, 0 ≤ m ≤ 200 000). Следующие m строк содержат пары u, v (1 ≤ u, v ≤ n, u ≠ v). Каждая неупорядоченная пара встречается не более одного раза.
Выходные данные
Выведите количество допустимых распределений по модулю 1 000 000 007.
Пояснения к примерам
Пример 1. У цепочки 1–2–3 два варианта смен, у наблюдателя 4 ещё два независимых варианта.
Пример 2. Трёх наблюдателей, попарно обязанных работать в разных сменах, в две смены распределить нельзя.
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 2
2 3
|
4
|
|
2
|
3 3
1 2
2 3
3 1
|
0
|