Беси и ее бычок решили соединить свои фермы дорожками, чтобы сформировать союз против фермеров. Коровы в каждой из N (1 <= N <= 100,000) ферм были изначально проинструктированы, чтобы построить одну дорожку ровно к одной другой ферме. Всего получилось N дорожек. Однако через несколько месяцев после начала проекта реально построены были только M (1 <= M < N) дорожек. Беси хочет узнать, сколькими способами могли быть построены эти M дорожек. Например, если между фермами 3 и 4 есть дорожка, Один способ, что ее построила ферма 3, другой - что ферма 4.
Помогите Беси посчитать количество способов назначения к дорожкам построивших их ферм по модулю 1 000 000 007. Два назначения рассматриваются как различные, если хоть одна дорожка построена разными фермами в этих двух назначениях.
PROBLEM NAME: alliance
Формат входных данных
* Строка 1: Два разделенных пробелами целых числа N и M
* Строки 2..1+M: Строка i+1 описывает i-ую дорожку. Каждая строка содержит два разделенных пробелом целых числа ui vi (1 <= ui, vi <= N, ui != vi), описывающих пару ферм, соединенных дорожкой.
Формат выходных данных
* Строка 1: Одна строка, содержащая число назначений дорожек фермам, взятое по модулю 1,000,000,007. Если не существует назначений, удовлетворяющих заданным условиям, выведите 0.
Примечание
Всего существует 6 возможных назначений. Обозначение {a,b,c,d} означает, что ферма 1 построила дорожку a, Ферма 2 построила дорожку b, ферма 3 построила дорожку c, а ферма 4 построила дорожку d. Эти 6 назначений таковы: {2, 3, 4, 5} {2, 3, 5, 4} {1, 3, 4, 5} {1, 3, 5, 4} {1, 2, 4, 5} {1, 2, 5, 4}
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
1 2
3 2
4 5
4 5
|
6
|