Вам, наверное, хорошо известна классическая задача о расстановке ферзей: на шахматной доске N×N требуется расставить N ферзей таким образом, чтобы никакие два ферзя не били друг друга. Такая расстановка ферзей называется мирной. Однако в данной задаче нас будет интересовать не какая-то одна мирная расстановка ферзей, а все различные мирные расстановки. Точнее, их общее количество. Например, для доски 8×8 существует 92 различных мирных расстановки ферзей.

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

Во входном файле записано единственное натуральное число N (N ≤ 12).

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

В выходной файл выведите искомое количество мирных расстановок ферзей.