N × N 크기의 체스판 위에 N개의 퀸(Queen)을 서로 공격할 수 없도록 배치하려고 합니다.

체스에서 퀸은 자신의 위치를 기준으로 가로, 세로, 그리고 대각선 방향(양방향 모두)으로 거리에 제한 없이 이동하며 공격할 수 있는 강력한 기물입니다.

자연수 N이 주어졌을 때, N개의 퀸을 서로 공격할 수 없게 배치하는 모든 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 체스판의 크기이자 퀸의 개수인 자연수 N이 주어진다.

출력

첫째 줄에 N개의 퀸을 서로 공격할 수 없도록 배치하는 모든 방법의 수를 출력한다.

제한 사항

• 3 ≤ N ≤ 9

예제 입력 1

4

예제 출력 1

2

예제 입력 2

3

예제 출력 2

0