Museum
In the capital city of Olympia, the Museum of Olympic Glory has been established to showcase the awards won by the country's schoolchildren in various subject Olympiads. The museum consists of exhibition halls interconnected by corridors, with each corridor linking exactly two halls. It is guaranteed that any hall in the museum can be reached from any other hall by traversing these corridors. Additionally, the number of corridors is equal to the number of halls.
At night, the museum is under the watch of guards. The number of guards is equal to the number of halls, with each guard stationed in a specific hall. Every hour, according to a predetermined patrol plan, some guards move to a different hall while others remain in place. The patrol plan adheres to the following conditions:
For each hall, the plan dictates whether its guard will stay or move to an adjacent hall connected by a corridor.
After the guards have moved, there must be exactly one guard in each hall.
The same patrol plan is repeated every hour.
For instance, the diagram illustrates one possible patrol plan. According to this plan, every hour, the guard in hall 1 moves to hall 2; the guard from hall 2 moves to hall 3; the guard from hall 3 moves to hall 1; the guards from halls 4 and 5 switch places, and the guard in hall 6 remains there throughout the night.
Write a program that, given the number of museum halls and their corridor connections, calculates the number of distinct patrol plans for the museum, modulo P.
Input
The first line contains two integers N (3 ≤ N ≤ 50000) - the number of halls in the museum, and P (2 ≤ P ≤ 10000). The following N lines each contain a pair of integers from 1 to N, representing the numbers of the halls connected by a corridor.
Output
Output a single integer - the number of patrol plans for the museum, modulo P (the remainder when the total number of plans is divided by P).
Explanation of the example: There are 20 different patrol plans: (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). The plan depicted in the diagram is (2, 3, 1, 5, 4, 6).