Задание

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

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

2.  К этой записи дописываются справа ещё два разряда по следующему правилу:  складываются все цифры двоичной записи числа M, и остаток от деления суммы на 2 дописывается в конец числа.

3. Над этой записью производятся те же действия  — в конец числа дописывается остаток от деления суммы цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа M) является двоичной записью результирующего числа S.

Пример. Запись 111002 преобразуется в запись 1110012, а затем в запись 11100102.

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