Мирные ферзи

Известно, что на шахматной доске размером 8×8 можно расставить 8 ферзей так, чтобы они не били друг друга. Попробуйте расставить n ферзей на шахматной доске размером n×n так, чтобы они не били друг друга.

Ваша программа должна определить количество способов это сделать.

Входные данные

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

Выходные данные

Программа должна вывести единственное число: количество расстановок мирных ферзей на доске n×n.

Примеры