Вам, напевне, добре відома класична задача про розстановку ферзів: на шаховій дошці N
×N
потрібно розставити N
ферзів таким чином, щоб ніякі два ферзі не били один одного. Така розстановка ферзів називається мирною. Проте у даній задачі нас буде цікавити не якась одна мирна розстановка ферзів, а усі різні мирні розстановки. Точніше, їх загальна кількість. Наприклад, для дошки 8×8 існує 92 різних мирних розстановок ферзів.
У вхідному файлі записано єдине натуральне число N
(N ≤ 12
).
У вихідний файл виведіть шукану кількість мирних розстановок ферзів.