Задача F. Числа и музыка

Автор:А. Кленин   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

"Музыкальная" последовательность, состоящая из нулей и единиц, строится следующим образом: на первом шаге последовательность состоит из одной единицы. На каждом следующем шаге к последовательности приписывается ее инверсия, т. е. последовательность, в которой 1 заменены на 0 и наоборот.

Таким образом, на первых 5 шагах последовательность будет выглядеть так:
1
10
1001
10010110
1001011001101001
Требуется по данному числу N определить значение N-го элемента последовательности.

Формат входного файла

Во входном файле содержится целое число N.

Формат выходного файла

В выходном файле должно содержаться число 0 (нуль) либо 1.

Ограничения

1 ≤ N ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
13
1

0.093s 0.024s 15