레드 존 게임

시간 제한2초메모리 제한128 MB

요약

무한 보드 위 n행 n열 폰 배치를 직교 점프로 뛰어넘은 폰을 제거하면서 하나의 폰으로 줄일 수 있는지 판정합니다.

문제

레드 존에게는 크기가 무한한 체스판과 폰 $n^2$ 개가 있다. 폰은 판 위에 $n \times n$ 정사각형 모양으로 놓여 있다.

폰은 가로나 세로로 인접한 폰 하나를 뛰어넘어 바로 그다음 칸으로 이동한다. 도착할 칸이 비어 있을 때만 이렇게 움직일 수 있고, 이동이 끝나면 뛰어넘긴 폰은 판에서 없어진다.

이 이동을 여러 번 해서 판에 폰을 하나만 남길 수 있는지 판단하라.

$n = 2$ 이면 세 번 움직여서 폰 하나만 남는다. 아래 그림에서 P는 폰, 점은 빈 칸이다.

P P .     . . P     . . P     . . .
P P .  -> P P .  -> . . P  -> . . .
. . .     . . .     . . .     . . P

첫째 줄에 정수 $n$ 이 주어진다. ( $0 < n < 10^9$ )

폰을 하나만 남길 수 있으면 1을, 그럴 수 없으면 0을 출력한다.