8478번 - Chessboard 다국어

문제

Byteasar admires chess puzzles. He is a long-time subscriber of the Chess Player's Magazine. The most recent issue of this magazine contains the following puzzle:

A chessboard of size n×n is given. In how many ways one can place n rooks on the chessboard, so that no two rooks attack each other and the i-th rook is located neither in the i-th column nor in the i-th row? The rooks, the rows and the columns are numbered from 1 to n. The result should be given modulo m.

Puzzles of the type "mate in 13 moves" are a piece of cake for Byteasar, but this new type of puzzle seems very hard for him. Could you please help him?

입력

The only line of input contains two integers n and m (1 ≤ n ≤ 1018, 1 ≤ m ≤ 10⁶).

출력

Your program should output the number of possible placements of rooks.

제한

힌트