Məsələlər
Музей
Музей
В столице страны Олимпия построен Музей Олимпийской Славы, в котором выставлены награды школьников страны с разных предметных олимпиад. Здание музея сосотоит из выставочных залов, соединённых коридорами. Коридор соединяет ровно два зала. Известно, что в каждый зал музея можно добраться из любого другого зала, идя по коридорам. Также известно, что количество коридоров равно количеству залов.
\includegraphics{https://static.e-olymp.com/content/a0/a098315e3bac8c16f29bf7c08e8b09a863b7dc9a.jpg}
Ночью музей патрулируется охранниками. Количество охранников равно количеству залов, и в кождый момент времени охранник смотрит за своим залом. Кождый час согласно плана патрулирования некоторые из охранников переходят в другой зал, а другие отсаются на месте. План патрулирования соответствует таким требованиям:
\begin{enumerate}
\item Для каждого зала план задаёт или остаётся его охранник на месте, или перейдёт в определённый зал, который соединён с текущим коридором.
\item После переходов охранников, в каждом зале должен оказаться ровно один охранник.
\item Каждый час применяется один и тот же план патрулирования.
\end{enumerate}
Например, на рисунке приведён один из возможных планов патрулирования. Согласно ему каждый час охранник, находящийся в зале \textbf{1}, переходит в зал \textbf{2}; охранник из залв \textbf{2} -- в зал \textbf{3}; из зала \textbf{3} -- в зал \textbf{1}; охранники из залов \textbf{4} и \textbf{5} меняются местами, а охранник из зала \textbf{6} всю ночь проводит в этом зале.
Напишите программу, которая по информации о количестве залов музею и соединения их коридорами найдёт количество разных планов патрулирования музея по модулю \textbf{P}.
\InputFile
Первая строка содержит пару целых чисел \textbf{N }(\textbf{3 }≤ \textbf{N }≤ \textbf{50000}) - количество залов в музее, и \textbf{P }(\textbf{2 }≤ \textbf{P }≤ \textbf{10000}). Последующие \textbf{N }с\textit{т}рок содержат пары целых чисел от \textbf{1 }до \textbf{N} - номера залов, соединённых коридором.
\OutputFile
Вывести одно целое число - количество планов патрулирования музея, по модулю \textbf{P }(остаток от деления искомого количества на \textbf{P}).
\textit{\textbf{Объяснение к примеру}}: Существует \textbf{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). На рисунке из условия изображён план (\textbf{2}, \textbf{3}, \textbf{1}, \textbf{5}, \textbf{4}, \textbf{6}).
Giriş verilənləri #1
6 1000 1 2 2 3 3 1 3 4 4 5 4 6
Çıxış verilənləri #1
20