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

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

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

Вхідні дані

Розмір шахової дошки $n(n\le 1000)$.

Вихідні дані

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

Приклади