pretty

Today is the sequence day! The math teacher wrote some sequences on the whiteboard, each having $N$ different numbers, all from $1$ to $N$, and told the students that these sequences had some special property. After some careful consideration, one of the students, Deni, guessed the correct property. All the sequences on the whiteboard had at least one pair of adjacent numbers in the form $(x, x + 1)$. Deni was so happy that she called this type of sequence pretty. For example, for $N = 4$ the sequences: $3, 1, 2, 4$ and $2, 3, 4, 1$ are pretty but the sequences $2, 4, 1, 3$ and $4, 3, 2, 1$ aren't. After that, the math teacher gave Deni a harder question. She was asked to calculate the number of all possible pretty sequences with $N$ different numbers, all from $1$ to $N$. This was so hard that Deni couldn't find an answer during the whole class. You are a friend of Deni and want to help her.

Task

Write a program which for a given $N$ has to tell Deni the number of pretty sequences. This number can be rather large, so you have to calculate it modulo $M$.

Input

From the first line of the standard input, read two integers $N$ and $M$ - the length of the sequences on the whiteboard and the module, used for the calculation.

Output

On one line of the standard output, the program has to write one integer - the number of pretty sequences with $N$ different numbers, all from $1$ to $N$, modulo $M$.

Constraints

• $1 ≤ N ≤ 10^{18}$
• $2 ≤ M ≤ 10^7$

Subtasks

Subtaks 1 (0 points)

• The examples.

Subtask 2 (9 points)

• $N ≤ 10$

Subtask 3 (14 points)

• $N ≤ 15$

Subtask 4 (11 points)

• $N ≤ 20$

Subtask 5 (43 points)

• $N ≤ 10^6$

Subtask 6 (23 points)

• $N ≤ 10^{18}$

Examples

stdin

4 42

stdout

13

Explanation

The pretty sequences with $4$ different numbers, all from $1$ to $4$, are:

1 2 3 4
1 3 4 2                                                                      
1 4 2 3                                                                      
2 1 3 4                                                                      
2 3 1 4
2 3 4 1                                                                               
3 1 2 4
3 4 2 1 
4 1 2 3 
4 2 3 1 
4 3 1 2 

stdin

2000 10009

stdout

1295

Explanation

Here the real answer is a large number whose remainder modulo $10009$ is $1295$.