레드 존 게임

레드 존에게는 크기가 무한한 체스판과 폰 $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을 출력한다.