Мирні ферзі

Відомо, що на шаховій дошці розміром 8×8 можна розставити 8 ферзів так, щоб вони не били один одного. Спробуйте розставити n ферзів на шаховій дошці розміром n×n так, щоб вони не били один одного.

Ваша програма повинна визначити кількість способів це зробити.

Вхідні дані

Програма отримує на вхід натуральне число n, яке не перевищує 10.

Вихідні дані

Програма повинна вивести єдине число: кількість розстановок мирних ферзів на дошці n×n.

Приклади