Rooks on a chessboard

From the childhood little Garik was interested in a question: in how many ways $n$ rooks can be arranged on the chessboard of size $n\times n$ so that they do not hit each other. He was solving this puzzle for a long time for each case, and when he solved the problem — he gave up the chess.

And how fast can you solve this puzzle?

Input

The size of the chessboard $n(n\le 1000)$.

Output

Print the answer, found by Garik.

Examples