Ладьи на шахматной доске

Ещё в детстве маленького Гарика заинтересовал вопрос: сколькими способами на шахматной доске размером $n\times n$ можно расставить $n$ ладей так, чтобы они не били друг друга. Он очень долго решал эту задачку для каждого варианта, а когда решил — бросил шахматы.

А как быстро Вы управитесь с этой задачкой?

Входные данные

Размер шахматной доски $n(n\le 1000)$.

Выходные данные

Выведите ответ, найденный Гариком.

Примеры