시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB319753.846%

문제

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 ≤ 106).

출력

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

예제 입력 1

3 120

예제 출력 1

4

출처

Camp > POI Training Camp > ONTAK 2010 5-3번