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 ≤ 10⁵; 1 ≤ p ≤ 10⁹ + 7).

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