Chessboard

Memory limit: 64 MB

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 is given. In how many ways one can place rooks on the chessboard, so that no two rooks attack each other and the -th rook is located neither in the -th column nor in the -th row? The rooks, the rows and the columns are numbered from to . The result should be given modulo .

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?

Input

The only line of input contains two integers and (, ).

Output

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

Example

For the input data:

3 120

the correct result is:

4

Task author: Tomasz Idziaszek.