Задание 5 ЕГЭ по информатике

На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом:

1. Строится двоичная запись числа $N$.

2. К этой записи дописываются разряды по следующему правилу:

a) если число четное, то к двоичной записи числа в конце дописываются 1 и 0;

b) если число нечетное, то к двоичной записи числа в конце дописывается 01.

Полученная таким образом запись является двоичной записью искомого числа $R$. Укажите наибольшее число $R$ меньшее 109, которое может получиться после обработки этого алгоритма. В ответе это число запишите в десятичной системе.