Задача Upgrade

 Как в любом большом городе, в нашем достаточно много школ, каждая имеет свой сервер. Некоторые из них соединены между собой каналами двусторонней прямой связи. Каждый из каналов соединяет непосредственно  2 школы, любые две школы соединены не более, чем одним каналом. Образование  не имеет достаточно средств, потому  к каждой  школе ведет не более двух каналов. В процессе  работы информация передается с сервера-«отправителя»  на сервер– «получатель» через некоторые из наявных каналов, причем неважно, через какие. Но  многие из существующих каналов обустроены давно и не предназначены для передачи информации с большой скоростью. Наша лаборатория приняла решенние заменить часть каналов оптоволоконными таким образом: если информация могла попадать с сервера A на сервер B, то теперь она сможет пройти  с А на В через оптоволоконные каналы. Конечно, оптическое волокно стоит дорого, потому мы хотим заменить минимальное количество старых «медных» каналов на новые оптоволоконные, а избыточные  «медные»  законсервировать. Понятно, что каждый сервер умеет, как и ранее, «роутить» информацию, то есть пропускать ее далее, если существует канал связи.

Очень хочется знать, сколько существует разных способов замены минимального количества каналов. Два способа считаются разными, если существует канал, который  заменили в одном из способов, и не заменили в другом. Помогите нам.

Технические условия.  Программа UPGRADE  читает с клавиатуры 2числа n і m (1<=n<=10⁵     0<=m<=10⁵) – количество школ и количество каналов соответственно. Далее программа читает вm строках  каналы, по одному в строке. Каждый канал задан двумя целыми числами  А_і и В_і (1<= А_і, В_і <=n,  А_і<>В_і) – номера школ, которые соединяет канал с номером і. Гарантировано, что каждый канал задан не более одного раза. Программа выводит на экран одно единственное число – количество способов замены. Поскольку число может быть достаточно большим, выводить нужно по модулю 10⁹+7(то есть - остаток от деления на это число).

Примеры