퀸을 놓는 방법

첫 줄에 정수 n (1 이상 11 이하) 이 주어집니다.

n × n 체스판에 퀸 n개를 서로 공격할 수 없게 놓는 방법의 수를 출력하세요.

퀸은 같은 행, 같은 열, 두 대각선에 있는 다른 퀸을 공격합니다. 한 방법도 없으면 0 을 출력합니다.

예시

입력

4

출력

2