Низ \(1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,\ldots,\) који се састоји од нула и јединица, гради се на следећи начин: први елемент је 1; други се добија логичком негацијом првог \(NOT(1)=0\), трећи и четврти логичком негацијом претходна два \(NOT(1)=0\), \(NOT(0)=1\), пети, шести, седми и осми логичком негацијом прва четири – добија се \(0,1,1,0\) итд. Дакле, кренувши од једночланог сегмента \(1\), сваком почетном сегменту који је дужине \(2^k\) (\(k\) узима вредности \(0, 1, 2, \ldots\)) дописује се сегмент исте дужине добијен логичком негацијом свих елемената почетног сегмента. За задато \(n\) одредити \(n\)-ти члан низа (бројање креће од 1).

Улаз

У првој линији стандардног улаза налази се природан број \(n\) (\(1 \leq n \leq 10^9\)).

Излаз

На стандарном излазу приказати цифру (0 или 1) на позицији \(n\)

Пример 1

Улаз

15

Излаз

0

Пример 2

Улаз

1234

Излаз

0

Пример 3

Улаз

12345678

Излаз

1