3. РобоЁжики
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Безумный гений доктор Шпунтик собирает армию боевых роботов-ёжиков из старого металлолома. Перед ним лежит огромная железная конструкция: $$$n$$$ круглых деталей-шестерёнок, которые соединены $$$m$$$ стальными прутьями (каждый прут соединяет ровно две детали). Чтобы активировать одного робота-ёжика, доктору нужно выбрать ровно одну деталь и несколько стальных прутьев, приваренных к этой детали (они станут «иголками»). Для того чтобы робот-ёжик считался правильным и готовым к работе, у него должно быть как минимум три иголки.

Шпунтику не нравится однообразная работа, поэтому каждый его робот должен быть уникальным. Два робота-ёжика считаются различными, если для них выбраны разные детали, или если у них отличается хотя бы одна иголка (выбраны разные наборы прутьев, торчащих из детали). Доктор хочет вычислить, сколько всего различных правильных роботов-ёжиков скрыто в его конструкции. Ёжиков настолько много, что без помощи Шпунтику не справиться. Так как количество роботов может быть очень большим, выведите ответ по модулю $$$10^9 + 7$$$.

Формально: вам дан неориентированный граф. Требуется вычислить количество подграфов вида «ёжик»: в них центральная вершина связана рёбрами с несколькими другими количеством не менее трёх, и других рёбер нет. Обратите внимание: в исходном графе вершины – концы «иголок» «ёжика» могут быть связаны рёбрами, просто при выделении подграфа «ёжик» они в него не включаются. «Ёжики» считаются различными, если есть хотя бы одна вершина, присутствующая в одном из них и отсутствующая в другом. Вам требуется вычислить остаток от деления количества «ёжиков» на число $$$10^9 + 7.$$$

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

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$n - 1 \le m \le 3 \cdot 10^5$$$) — количество деталей и прутьев в конструкции соответственно. В следующих $$$m$$$ строках содержатся описания прутьев. Каждая строка содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — начало и конец прута. Гарантируется, что конструкция связная и описания прутьев не повторяются.

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

Выведите одно целое число — количество различных роботов-ёжиков в заданной конструкции по модулю $$$10^9 + 7$$$ (то есть остаток от деления на $$$10^9 + 7$$$).

Система оценки

Подзадача 1 (до 20 баллов): $$$n, m \le 15$$$

Подзадача 2 (до 24 баллов): $$$n, m \le 2000$$$

Подзадача 3 (до 56 баллов): $$$n, m \le 3 \cdot 10^5$$$

Примеры
Входные данные
4 3
1 2
1 3
1 4
Выходные данные
1
Входные данные
5 4
1 2
1 3
1 4
1 5
Выходные данные
5
Примечание

Примечание по языку Python. Два числа, записанных через пробел, можно прочитать так:

n, m = map(int, input().split())