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