Chessboard

Time limit1sMemory limit128 MB

Summary

Count permutations of 1..n whose i-th rook avoids row i and column i, modulo m.

Level: Hard8 of 10
Topics: Combinatorics, Dynamic programming, Math
Solved: No attempts yet

Problem

Byteasar loves chess puzzles. He has subscribed to a chess magazine for years, and its latest issue features the following puzzle.

You are given a chessboard of size $n \times n$ . In how many ways can you place $n$ rooks on the board so that no two rooks attack each other (that is, no two share a row or a column) and, for every $i$ , the $i$ -th rook lies in neither the $i$ -th row nor the $i$ -th column? The rooks, the rows, and the columns are all numbered from $1$ to $n$ . Report the answer modulo $m$ .

Puzzles like "mate in 13 moves" are a piece of cake for Byteasar, but this new kind of puzzle looks very hard to him. Could you help him?

Input

The first line contains two integers $n$ and $m$ separated by a space ( $1 \le n \le 10^{18}$ , $1 \le m \le 10^{6}$ ).

Output

Print, on a single line, the number of valid rook placements modulo $m$ .

Examples4

Example 1
Input
```
3 120
```
Expected output
```
4
```
Example 2
Input
```
1 120
```
Expected output
```
0
```
Example 3
Input
```
2 120
```
Expected output
```
1
```
Example 4
Input
```
4 120
```
Expected output
```
81
```