Toy

Time Limit: 8000 ms Memory Limit: 32768 KiB

Problem Description

On birthday, Anthony got a toy. It is constructed with N+1(N>=3) balls and 2*N sticks. All balls are in a same plane. One of them is special, while the other N balls are connected to it by N sticks with the same length. The angles between any two adjacent sticks are equal. And finally, any two adjacent balls(except the central one) are connected by a stick.

Here are two examples:

Anthony wanted to remove N sticks, leaving all balls still connected. He wanted to know the number of all legal solutions. Your task is to solve this problem for him.

Notice that if a solution will be the same as another one by rotation, these two solutions should be consider as the same.

The answer may be quite large. You just need to calculate the remainder of the answer when divided by M.

Input

Input contains several test cases.

For each test case, there is only one line containing two integers N and M(3<=N<=10^9, 2<=M<=10^9).

Input is terminated by EOF.

Output

For each case, output one integer in one line, representing the remainder of the number of all solutions when divided by M.

Sample Input

3 10000
4 10000
4 10

Sample Output

6
13
3

Hint

hdoj2481 有链接提示的题目请先去链接处提交程序,AC后提交到SDUTOJ中,以便查询存档。

Source

四川回锅肉——2008成都现场赛题目