# Rooks on a chessboard

Very easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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?

## Input

The size of the chessboard $n(n≤1000)$.

## Output

Print the answer, found by Garik.

## Examples

Input #1

Answer #1

Submissions 5K

Acceptance rate 37%