8 퀸 문제로도 유명한 이 문제는 N*N 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제입니다. 

퀸은 체스에서 가장 강력한 말인데, 자신의 위치에서 상하좌우 그리고 대각선 방향을 자유롭게 이동하거나 공격할 수 있습니다.

(출처: 8퀸 문제, 위키피디아)

위 그림은 8*8 사이즈 체스판에서 8개의 퀸이 서로 공격할 수 없도록 배치한 예 중 하나입니다.

체스판의 크기를 입력하고 N Queen's Problem의 해가 몇개가 나오는지를 계산하는 프로그램을 작성하십시오 ( N은 1 이상 14 이하 ).

*N이 2,3인 경우를 제외하고 해를 찾을 수 있습니다.

입력

1 이상 14이하 정수

출력

입력 * 입력 크기의 체스판에서 N Quuen's 문제의 해 개수