Red John Game

Red John has a chessboard of infinite size and $n^2$ pawns, arranged on the board in an $n \times n$ square.

A pawn moves by jumping over a horizontally or vertically adjacent pawn and landing on the cell right behind it. The move is allowed only when that landing cell is empty, and the pawn that was jumped over is taken off the board.

Decide whether some sequence of these moves leaves exactly one pawn on the board.

For $n = 2$, three moves leave one pawn. In the diagram below, P is a pawn and a dot is an empty cell.

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

The first line contains the integer $n$. ($0 < n < 10^9$)

Print 1 if the pawns can be reduced to a single pawn, and 0 if they cannot.