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