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