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

Наприклад, для дошки 8 × 8 існує 92 різних мирних розстановок ферзів.

Формат вхідних даних

У вхідному потоці записано єдине натуральне число ~N~ ~(N ≤ 12)~.

Формат вихідних даних

У вихідний потік виведіть шукану кількість мирних розстановок ферзів.

Приклад вхідних даних

8

Приклад вихідних даних

92