Problem description

Dana jest szachownica N × N i N szachowych hetmanów. Hetman szachuje pola, które leżą w tym samym wierszu, kolumnie bądź na przekątnej.

Napisz program, który: wczyta N, wyznaczy liczbę sposobów ustawienia N nieszachujących się hetmanów na szachownicy N × N i wypisze wynik na wyjście.

Wejście

W pierwszym (i jedynym) wierszu wejścia znajduje się jedna liczba naturalna N.

Wyjście

W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – liczba sposobów ustawienia N hetmanów na szachownicy N × N.

Ograniczenia

1 ≤ N ≤ 12.

Przykład

4

2