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