Музей
У столиці країни Олімпія збудований Музей Олімпійської Слави, де виставлено нагороди школярів країни з різних предметних олімпіад. Будівля музею складається з виставкових залів, з’єднаних коридорами. Коридор сполучає рівно два зали. Відомо, що кожного залу музею можна дістатися з будь-якого іншого залу, прямуючи коридорами. Також відомо, що кількість коридорів дорівнює кількості залів.
Вночі музей патрулюється охоронцями. Кількість охоронців дорівнює кількості залів, та у кожен момент часу охоронець доглядає за своїм залом. Кожну годину згідно плану патрулювання деякі з охоронців переходять в іншу залу, а інші залишаються на місті. План патрулювання відповідає таким вимогам:
Для кожної зали план задає чи залишиться її охоронець на місці, чи перейде до певної зали, яка сполучена з поточною коридором.
Після переходів охоронців, у кожній залі повинен опинитися рівно один охоронець.
Кожну годину застосовується один і той самий план патрулювання.
Наприклад, на рисунку наведений один з можливих планів патрулювання. Згідно йому кожну годину охоронець, що знаходиться у залі 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).