Ещё в детстве маленького Гарика заинтересовал вопрос: сколькими способами на шахматной доске размером n×n можно расставить n ладей так, чтобы они не били друг друга. Он очень долго решал эту задачку для каждого варианта, а когда решил — бросил шахматы.
А как быстро Вы управитесь с этой задачкой?
Размер шахматной доски n (n≤1000).
Выведите ответ, найденный Гариком.