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

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

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

Размер шахматной доски - натуральное число, не превышающее 1000.

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

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