Задание

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

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

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

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

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

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

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

При каком наименьшем числе M в результате работы алгоритма получится S > 4010. В ответе запишите это число в десятичной системе счисления.