N-Queens: Count Solutions

Larkspur Games is shipping a chess puzzle and needs the answer key. On an n by n board, n queens have to be placed so that no queen can capture another. A queen captures along her whole row, her whole column, and both diagonals, for any distance. Two arrangements count as different whenever any queen stands on a different square, so a board that is a rotation or mirror image of another is still a second arrangement.

Task: Print how many different arrangements exist.

Input

A single line holding one integer n, between 1 and 9. This is both the board's width and the number of queens to place.

Output

One line holding a single integer: the number of arrangements in which no queen can capture another. Count every arrangement separately, including ones that are rotations or mirror images of each other. Print 0 if no arrangement exists.

Example:

Input:
4

Output:
2