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×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?
The size of the chessboard n (n≤1000).
Print the answer, found by Garik.