ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ufa SATU contest. Petrozavodsk training camp. Summer 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Kingdom Inspection

Time limit: 1.0 second
Memory limit: 64 MB
A long time ago there was a King in Three-binary Kingdom… He had a few years left to live and he decided to make one last journey around his kingdom to see what was going on there.
Kingdom had n towns and each pair of them was connected by exactly one bidirectional road. One of the towns was a capital where the King lived.
The King was very old and his memory often played a bad joke with him. That was why the King decided to make a journey. He was going to visit each town exactly twice, just in case. His journey should begin and end at the capital.
While the King had been choosing the best option for the journey, he encountered an interesting question: how many different routes for the journey exists so that each of the earlier mentioned conditions is met?


The first line contains two space-separated integers n and p (3 ≤ n ≤ 105; 1 ≤ p ≤ 109 + 7).


Output the answer for the King's question modulo p.


3 123
4 123
Problem Author: Artyom Ripatti
Problem Source: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009
To submit the solution for this problem go to the Problem set: 1747. Kingdom Inspection