Купол четырёх стихий

В королевстве Элерион четыре перво-стихии — Огонь, Вода, Воздух и Земля. Во время затмения маги-хранители возводят вокруг столицы защитный купол. Для этого они соединяют себя потоками стихий: каждый маг может передать силу ровно одной из четырёх стихий (а может и вовсе ничего не передавать) и может принять силы от не более чем трёх других магов — по одному потоку в оставшиеся стихийные каналы.

Верховный маг дал чертёж будущего купола в виде неориентированного графа из N вершин и M рёбер:

• вершины — маги,
• ребро — поток стихии, который должен существовать между двумя магами.

Нужно посчитать, сколькими различными способами можно направить все потоки (то есть выбрать их направления), чтобы получилась корректная сеть.

Ограничения на сеть:

• Петли запрещены — поток не может идти от мага к самому себе.
• У одного мага не более одного исходящего потока (он «отдаёт» только по одному каналу).
• В каждого мага может «войти» не более трёх потоков (остальные три канала). Поскольку общее число каналов у мага равно 4.
• Нельзя проложить два потока между одной и той же парой магов в противоположных направлениях.

Два способа считаются разными, если найдётся пара магов (A, B), для которой поток направлен A → B в одном варианте и наоборот — в другом. Какой именно стихии поток принадлежит, значения не имеет — важно только направление.

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

Входной файл INPUT.TXT содержит в первой строке два натуральных числа N, M (1 ≤ N, M ≤ 10⁶). Далее в M строках по два числа x, y – номера вершин, соединённых ребром (1 ≤ x, y ≤ N).

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

В выходной файл OUTPUT.TXT выведите ответ на задачу по модулю 10⁹ + 7.

Примеры

Пояснения к примерам

В первом примере:

Во втором примере:

Автор задачи

Владимир Игоревич Лукьянчиков

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

[Обсуждение] [Все попытки] [Лучшие попытки]