Problem Description

There is an infinite grid, and an ant is initially at coordinate $ (0,0) $. Each integer coordinate can be written with a number $ 0 $ or $ 1 $, and initially, all coordinates are written with $ 0 $. The ant starts facing upwards (positive direction of the $ Y $ axis) and will repeat the following actions indefinitely:

• If the number written at the current coordinate is $ 0 $, turn $ 90 $ degrees to the right; if it is $ 1 $, turn $ 90 $ degrees to the left.
• Invert the number written at the current coordinate. That is, if the original number is $ 0 $, write $ 1 $; if it is $ 1 $, write $ 0 $.
• Take one step forward. That is,
• If the ant is at coordinate $ (x,y) $ and facing upwards, move to coordinate $ (x,y+1) $.
• If the ant is at coordinate $ (x,y) $ and facing to the right, move to coordinate $ (x+1,y) $.
• If the ant is at coordinate $ (x,y) $ and facing downwards, move to coordinate $ (x,y-1) $.
• If the ant is at coordinate $ (x,y) $ and facing to the left, move to coordinate $ (x-1,y) $.

After the ant has taken $ N $ steps, determine the number written at the coordinate where the ant is located.

Input Format

The input is given from the standard input in the following format:

$ N $

• The first line contains an integer $N\ (1\ ≦\ N\ ≦\ 10^{18})$ representing the number of steps.

Output Format

Output the number written at the coordinate where the ant is located after taking $ N $ steps. The output should be on one line, followed by a newline.

Sample Input and Output

Sample Input #1

5

Sample Output #1

0

Sample Input #2

9

Sample Output #2

1

Sample Input #3

314159

Sample Output #3

1

Sample Input #4

12345678987654321

Sample Output #4

0

Notes/Hints

Sample Explanation 1

The state of the grid up to the 10th step is as follows, where a represents the position of the ant:

00000
00000
00a00
00000
00000
00000
00000
001a0
00000
00000
00000
00000
00110
000a0
00000
00000
00000
00110
00a10
00000
00000
00000
00a10
00110
00000
00000
00000
0a010
00110
00000
00000
0a000
01010
00110
00000
00000
01a00
01010
00110
00000
00000
01100
01a10
00110
00000
00000
01100
0a110
00110
00000
00000
01100
00110
0a110
00000

见题面 Input 部分

见题面 Output 部分