Тури на шаховій дошці#1327
З дитинства маленького Гарика цікавило одне питання: скількома способами можна розставити тур на шахівниці розміром n \times n так, щоб вони не атакували одна одну? Він довго розв'язував цю загадку для кожного випадку; і коли нарешті вирішив її, покинув шахи.
А як швидко впораєтеся з цим завданням ви?
Розмір шахівниці (n \le 1000).
Виведіть відповідь, яку знайшов Гарик.
Приклад 1