Migrated from Lutece 1400 Bigger world

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

As a new employee at the IEEE , you do a lot of thinking about wireless network architectures. Lately you learned about a multi-channel mesh network architecture (called Hyacinth) to increase the network. There $n$ node,and each pair of them was connected by exactly one bidirectional line.

Your bosses at IEEE want you to make the network better.They ask you to find a path to passes all node twice.The first node and the end node is node $1$.Since you are clever,you finish the task.And you tell your bosses how many ways you can do it.

So how many paths you find to satisfy your bosses' require.

Input

The first line contains two space-separated integers $n$ and $p$ $(3 ≤ n ≤ 10^5; 1 ≤ p ≤ 10^9 + 7)$.

Output

For each test case, print a single line contains the answer modulo $p$.

Samples

3 1000000007

2

4 1000000007

30

Note

The sample 1:

1-2-3-2-3-1

1-3-2-3-2-1

Resources

IEEEXTREME Programming Competition