시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 4 3 100.000%

문제

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.

예제 입력

3 120

예제 출력

4

힌트