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

1747. 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?

Input

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

Output

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

Samples

inputoutput
3 123
2
4 123
30
Problem Author: Artyom Ripatti
Problem Source: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009