Garden Trees Arrangement

You are given an n x n garden. Your task is to determine the number of ways to plant exactly one tree in each row and each column such that no two trees share the same row, same column, or the same diagonal.

This problem is a variation of the famous N-Queens problem. In other words, place n trees on an n x n grid so that no two trees threaten each other. Two trees threaten each other if they are in the same row, the same column, or on the same diagonal.

The constraint can be mathematically represented as follows: for any two trees placed at positions \((r_1, c_1)\) and \((r_2, c_2)\), they must satisfy:

[ \begin{aligned} & r_1 \neq r_2,\ & c_1 \neq c_2,\ & |r_1 - r_2| \neq |c_1 - c_2| \end{aligned} ]

Your program should read an integer n from stdin and output the number of valid ways to arrange the trees on stdout.

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 15), representing the dimensions of the garden.

stdin:
n

outputFormat

Output a single integer, the number of ways to plant the trees such that no two trees are in the same row, column, or diagonal.

stdout:
result

## sample

1

1