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.