Задача J. Без двух единиц подряд ≡

Условие

Артём и Женя играют в следующую игру: они по очереди называют натуральные числа в порядке возрастания, которые в своей двоичной записи не имеют двух единиц подряд. Такими числами, например, будут 1, 2, 4, 5, 8 и так далее. А вот числа 3 = 11₂, 6 = 110₂ или 7 = 111₂ игроки пропускают.

Артём только что назвал число n. Какое число следует назвать Жене, чтобы продолжить игру?

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

Единственная строка входных данных содержит натуральное число n. Гарантируется, что в его двоичном представлении нет двух единиц подряд.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

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

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10¹⁷

Пояснение к примеру

В примере дано n = 9 = 1001₂. Следующее число n + 1 = 10 = 1010₂ тоже не имеет двух единиц подряд в своей двоичной записи.

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

9

10

Разбор

Найдём в двоичном представлении числа n первую справа позицию, состоящую из двух нулей подряд, то есть строка двоичного представления n имеет вид:

s = *00101..., где * - любые символы, а ... - чередующиеся единицы и нули.

Заменим найденное 00 на 01, а все следующие цифры сделаем нулями.

Если же в двоичном представлении числа n нет ни одной позиции, состоящей из двух нулей подряд, то есть строка двоичного представления n имеет вид: s = 1010..., где чередуются единицы и нули, тогда следующее число, подходящее под описание, будет иметь вид 100...00 (одна единица и столько нулей, сколько цифр в двоичном представлении числа n).