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

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

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

2.  В конец двоичной записи добавляются две цифры, соответствующие двоичной записи остатка от деления исходного числа на 3.

3.  В конец двоичной записи числа, полученного на предыдущем шаге, добавляются три цифры, соответствующие двоичной записи остатка от деления этого числа на 5.

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

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

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

2.  Остаток от деления 13 на 3 равен 1, добавляем к двоичной записи цифры 01, получаем 110101₂  =  53₁₀.

3.  Остаток от деления 53 на 5 равен 3, добавляем к двоичной записи цифры 011, получаем 110101011₂  =  427₁₀.

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

Определите количество принадлежащих отрезку [1 111 111 110; 1 444 444 416] чисел, которые могут получиться в результате работы этого алгоритма.