e-olymp
Задачі

Тури на шаховій дошці

Тури на шаховій дошці

prb1327

Ще у дитинстві маленького Гаріка зацікавило питання: а скількома способами на шаховій дошці розміром n × n можна розставити n тур так, щоб вони не били одна одну. Він дуже довго розв'язував цю задачку для кожного варіанту, а коли розв'язав - закинув шахи.

А як швидко Ви справитесь з цією задачкою?

Вхідні дані

Розмір шахової дошки - натуральне число, яке не перевищує 1000.

Вихідні дані

Виведіть відповідь, знайдену Гаріком.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
2
Вихідні дані #1
2