Задача E. Последовательность Морса-Туэ ≡

Автор:	П. Пруэ, А. Туэ, М. Морс		Ограничение времени:	2 сек
Входной файл:	input.txt		Ограничение памяти:	256 Мб
Выходной файл:	output.txt
Максимальный балл:	100

Условие

Последовательность Морса-Туэ задаётся следующим образом: 1) Вначале записывается 1. 2) Каждым шагом дописывается число, дополняющее уже написанное до числа, состоящего только из единиц. 3) Получаем искомую бесконечную последовательность: 1001011001101001011010011001011001101001...

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

В первой строке входного файла находится число N.

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

Выведите элемент последовательности Морса-Туэ с номером N.

Ограничения

1 ≤ N ≤ 10¹⁵

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

№	Входной файл (input.txt)	Выходной файл (output.txt)
1	1 скопировать	1 скопировать
2	2 скопировать	0 скопировать

---