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