eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Задача о ферзях

Задача о ферзях

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Вам, наверное, хорошо известна классическая задача о расстановке ферзей: на шахматной доске N×N требуется расставить N ферзей таким образом, чтобы никакие два ферзя не били друг друга. Такая расстановка ферзей называется мирной. Однако в данной задаче нас будет интересовать не какая-то одна мирная расстановка ферзей, а все различные мирные расстановки. Точнее, их общее количество. Например, для доски 8×8 существует 92 различных мирных расстановки ферзей.

Входные данные

Во входном файле записано единственное натуральное число N (N ≤ 12).

Выходные данные

В выходной файл выведите искомое количество мирных расстановок ферзей.

Пример

Входные данные #1
8
Выходные данные #1
92