Ще у дитинстві маленького Гаріка зацікавило питання: а скількома способами на шаховій дошці розміром n×n можна розставити n тур так, щоб вони не били одна одну. Він дуже довго розв'язував цю задачку для кожного варіанту, а коли розв'язав — закинув шахи.
А як швидко Ви справитесь з цією задачкою?
Розмір шахової дошки n (n≤1000).
Виведіть відповідь, знайдену Гаріком.