N-Queen

N-Queen 문제는 $N \times N$ 크기의 체스판에 퀸 $N$개를 서로 공격하지 못하게 놓는 문제이다. 퀸은 자신과 같은 행, 같은 열, 같은 대각선에 놓인 다른 퀸을 공격한다.

$N$이 주어졌을 때, 퀸 $N$개를 놓는 방법의 수를 구하는 프로그램을 작성하시오. 회전하거나 뒤집어서 서로 같아지는 배치도 각각 다른 방법으로 센다.

첫째 줄에 $N$이 주어진다. ($1 \le N < 15$)

첫째 줄에 퀸 $N$개를 서로 공격하지 못하게 놓는 방법의 수를 출력한다.