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:</p>

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.

예제 입력

3 120

예제 출력

4