시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 2 2 2 100.000%

문제

체스에서 퀸은 다른 말을 압도한다. 일단 퀸은 비숍과 룩의 기술을 모두 배웠다. 따라서, 퀸은 가로, 세로, 대각선으로 자신이 원하는 만큼 이동할 수 있다. 하나의 퀸이 많은 지역을 갈 수 있으므로, 체스판에 여러 개의 퀸을 서로를 잡지 않게 놓는 것은 어렵다. 이런 이유 때문에, N*N크기의 체스판에 N개의 퀸을 놓는 유명한 문제인 N-Queen문제가 탄생했다. 

이 문제를 위해 아래와 같은 랜덤 방법을 구현해야 한다. 체스판은 가장 왼쪽 열이 1이고, 가장 오른쪽 열이 N이다.

  1. 1보다 크거나 같고, N보다 작거나 같은 수 R을 랜덤하게 선택한다.
  2. 퀸을 R번 줄, 현재 열에 놓는다. (1번 줄이 가장 위, N번이 가장 아래)

약간 변형된 단계는 다음과 같다.

  1. 다른 퀸을 잡아먹을 수 있는 퀸의 수를 센다. 이 수를 T라고 한다.
  2. 1보다 크거나 같고, T보다 작거나 같은 수 중 랜덤하게 K를 고른다. C는 다른 퀸을 잡아먹을 수 있는 퀸이 있는 열 중 왼쪽에서 K번째 열을 말한다. 이와 같이 하게 되면 우리는 다른 퀸을 잡아먹을 수 있는 퀸 하나를 선택할 수 있게 된다.
  3. C열의 N개의 위치에서 얼마나 많은 퀸이 그 위치까지 도달할 수 있는지를 계산한다.
  4. C열에 있는 퀸을 3번에서 계산한 수 중에 가장 작은 값이 있는 행으로 이동시킨다. 여러개가 있으면 5번 단계를 실행한다.
  5. P를 계산한다. P는 위 4번에서 가장 작은 값이 있는 행의 개수이다.
  6. 1보다 크거나 같고, P보다 작거나 같은 수 중 하나를 랜덤하게 선택한다. 이 수를 Q라고 하자. 위에서부터 Q번째 줄(가장 작은수의 행만 센다.)

변형된 단계는 아무런 움직임이 없을 수도 있다. 이 문제는 얼마나 많은 변형된 단계를 거처야 모든 퀸이 서로 안 잡아먹는지를 구하는 것이다. I번째 랜덤값은 다음과 같이 구한다. (A[i]%Up)+1이다. Up은 위에서 구할 때 상한 한계이다. A[i]는 다음과 같이 구한다.

  • A[1] = 1
  • A[i+1] = (16807*A[i])%2147483647 (i>0)

%는 나머지연산이다. 이 랜덤값은 퀸을 놓을 때와 변형된 단계를 수행할 때 모두 쓰인다. 변형된 단계에서 5단계는 꼭 할 필요가 없으면 할 필요가 없고, 변형된 단계를 수행할 필요가 없으면 0을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 4보다 크거나 같고, 100보다 작거나 같은 자연수이다. 단, 17은 아니다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력

5

예제 출력

4

힌트

출처