Задание

Алгоритм получает на вход натуральное число M и строит по нему новое число S следующим образом:

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

2. Полученная запись обрабатывается по следующему правилу:

а) если сумма цифр в двоичной записи числа чётна, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 1;

б) если сумма цифр в двоичной записи числа нечётна, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11.

Полученная таким образом запись является двоичной записью искомого числа S.

Пример. Для исходного числа 610 = 1102 результатом является число 1002 = 410,

а для исходного 410 = 1002 результатом является число 11012 = 1310.

Укажите число M, после обработки которого с помощью этого алгоритма получается наименьшее значение S, большее 2510. В ответе запишите это число в десятичной системе счисления.