Алгоритм получает на вход натуральное число M и строит по нему новое число S следующим образом:
1. Строится двоичная запись числа M.
2. Складываются все цифры полученной двоичной записи. В конец записи дописывается остаток от деления суммы на 2.
3. Предыдущий пункт повторяется для записи с добавленной цифрой.
4. Результат переводится в десятичную систему.

Пример. Дано число M = 1310. Алгоритм работает следующим образом:
1. Двоичная запись числа M: 11012.
2. Сумма цифр двоичной записи 3, остаток от деления на 2 равен 1, новая запись 110112.
3. Сумма цифр полученной записи 4, остаток от деления на 2 равен 0, новая запись 1101102.
4. Результат работы алгоритма S = 5410.

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