Задание 5 ЕГЭ, информатика: Посимвольное двоичное преобразование

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

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

2.  Если сумма цифр десятичной записи заданного числа нечётна, то в конец двоичной записи дописывается 1, если чётна  — 0.

3−4.  Пункт 2 повторяется для вновь полученных чисел ещё два раза.

5.  Результатом работы алгоритма становится десятичная запись полученного числа R.

Пример. Дано число N  =  17. Алгоритм работает следующим образом:

1.  Строим двоичную запись: 17₁₀  =  10001₂.

2.  Сумма цифр числа 17 чётная, дописываем к двоичной записи 0, получаем 100010₂  =  34₁₀.

3.  Сумма цифр числа 34 нечётная, дописываем к двоичной записи 1, получаем 1000101₂  =  69₁₀.

4.  Сумма цифр числа 69 нечётная, дописываем к двоичной записи 1, получаем 10001011₂  =  139₁₀.

5.  Результат работы алгоритма R  =  139.

Определите количество принадлежащих отрезку [123 456 789; 1 987 654 321] чисел, которые могут получиться в результате работы этого алгоритма.