问题文

有一个无限广阔的网格，坐标$(0,0)$上有一只蚂蚁。每个整数坐标位置上可以写入数字$0$或者$1$，初始情况下所有坐标上都写着$0$。初始时，蚂蚁朝向上方（$Y$轴正方向），并且执行以下动作无限循环：

• 如果当前所在位置写着数字$0$，则右转$90$度；
• 如果当前所在位置写着数字$1$，则左转$90$度；
• 反转当前所在位置的数字。即，如果原来是$0$，则写入$1$；如果原来是$1$，则写入$0$；
• 前进$1$步。具体操作如下：
  • 如果蚂蚁在坐标$(x,y)$上且朝上方，则移动到坐标$(x,y+1)$；
  • 如果蚂蚁在坐标$(x,y)$上且朝右方，则移动到坐标$(x+1,y)$；
  • 如果蚂蚁在坐标$(x,y)$上且朝下方，则移动到坐标$(x,y-1)$；
  • 如果蚂蚁在坐标$(x,y)$上且朝左方，则移动到坐标$(x-1,y)$。

求在蚂蚁前进了$N$步之后，蚂蚁所在坐标上写着的数字。

输入

从标准输入读入数据。

输入的格式如下：

$N$

• 第 $1$ 行包含一个整数 $N (1 ≦ N ≦ 10^{18})$，表示步数。

输出

输出蚂蚁前进了$N$步之后，蚂蚁所在坐标上写着的数字。

输入例子1

5

输出例子1

0

蚂蚁前进到第$10$步时，网格状态如下图所示。其中，a表示蚂蚁的位置。

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

输入例子2

9

输出例子2

1

输入例子3

314159

输出例子3

1

输入例子4

12345678987654321

输出例子4

0