Музей
В столице страны Олимпия построен Музей Олимпийской Славы, в котором выставлены награды школьников страны с разных предметных олимпиад. Здание музея сосотоит из выставочных залов, соединённых коридорами. Коридор соединяет ровно два зала. Известно, что в каждый зал музея можно добраться из любого другого зала, идя по коридорам. Также известно, что количество коридоров равно количеству залов.
Ночью музей патрулируется охранниками. Количество охранников равно количеству залов, и в кождый момент времени охранник смотрит за своим залом. Кождый час согласно плана патрулирования некоторые из охранников переходят в другой зал, а другие отсаются на месте. План патрулирования соответствует таким требованиям:
Для каждого зала план задаёт или остаётся его охранник на месте, или перейдёт в определённый зал, который соединён с текущим коридором.
После переходов охранников, в каждом зале должен оказаться ровно один охранник.
Каждый час применяется один и тот же план патрулирования.
Например, на рисунке приведён один из возможных планов патрулирования. Согласно ему каждый час охранник, находящийся в зале 1, переходит в зал 2; охранник из залв 2 – в зал 3; из зала 3 – в зал 1; охранники из залов 4 и 5 меняются местами, а охранник из зала 6 всю ночь проводит в этом зале.
Напишите программу, которая по информации о количестве залов музею и соединения их коридорами найдёт количество разных планов патрулирования музея по модулю P.
Входные данные
Первая строка содержит пару целых чисел N (3 ≤ N ≤ 50000) - количество залов в музее, и P (2 ≤ P ≤ 10000). Последующие N строк содержат пары целых чисел от 1 до N - номера залов, соединённых коридором.
Выходные данные
Вывести одно целое число - количество планов патрулирования музея, по модулю P (остаток от деления искомого количества на P).
Объяснение к примеру: Существует 20 разных планов патрулирования: (1, 2, 3, 4, 5, 6), (1, 2, 3, 5, 4, 6), (1, 2, 3, 6, 5, 4), (1, 2, 4, 3, 5, 6), (1, 3, 2, 4, 5, 6), (1, 3, 2, 5, 4, 6), (1, 3, 2, 6, 5, 4), (2, 1, 3, 4, 5, 6), (2, 1, 3, 5, 4, 6), (2, 1, 3, 6, 5, 4), (2, 1, 4, 3, 5, 6), (2, 3, 1, 4, 5, 6), (2, 3, 1, 5, 4, 6), (2, 3, 1, 6, 5, 4), (3, 1, 2, 4, 5, 6), (3, 1, 2, 5, 4, 6), (3, 1, 2, 6, 5, 4), (3, 2, 1, 4, 5, 6), (3, 2, 1, 5, 4, 6), (3, 2, 1, 6, 5, 4). На рисунке из условия изображён план (2, 3, 1, 5, 4, 6).