Задание

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

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

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

Пример. Двоичная запись 1002 числа 410 будет преобразована в 100012, а двоичная запись 1112 числа 710 будет преобразована в 111102. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа M) является двоичной записью числа S – результата работы данного алгоритма.

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