Задача C. Бескончная строка ≡

Условие

Тимофей выписал все натуральные числа, перевёл каждое в двоичную систему счисления и записал подряд без пробелов. В результате получилась строка 1101110010111011110001001... Определите, какой символ находится на n-й позиции.

Формат входных данных

Единственная строка входных данных содержит натуральное число n.

Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Формат выходных данных

Выведите одну двоичную цифру — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10¹⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 10⁵, получат не менее 60 баллов.

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

3

0