Вася на уроке информатики узнал про различные системы счисления и, вдохновившись, придумал свой собственный способ кодирования чисел.
Для кодирования числа n подбирается такая сумма степеней двойки, чтобы в сумме получилось число n. При этом каждую из степеней двойки можно домножить на любую цифру от 0 (включительно) до 9 (включительно). Таким образом, многие числа можно представить как сумму степеней, домноженных на разные цифры, разными способами, например:
\(39 = 2^5 \cdot 1 + 2^0 \cdot 7 = 2^4 \cdot 2 + 2^0 \cdot 7 = 2^4 \cdot 2 + 2^2 \cdot 1 + 2^0 \cdot 3 = \ldots\)
После того как для числа n подобраны степени двойки и цифры, на которые эти степени домножаются, определяется максимальная степень двойки, которая участвует в сумме, и к этому числу прибавляется «1» — столько разрядов будет в финальном числе, обозначим это количество разрядов как r. Далее разряды закодированного числа нумеруются с 0 и до r−1. На каждую позицию записывается цифра, на которую домножалась соответствующая степень двойки.
Например, если сумма 39 была подобрана как \(2^5 \cdot 1 + 2^0 \cdot 7\), то количество разрядов r = 5+1 = 6, и число записывается в виде 700001. А если сумма 39 была подобрана как \(2^4 \cdot 2 + 2^2 \cdot 1 + 2^0 \cdot 3\), то число будет записано уже в виде 30102.
Теперь Вася задался вопросом, как закодировать своим способом число 71 так, чтобы сумма цифр результата кодирования при интерпретировании его как десятичного числа была минимальным возможным числом. В ответ запишите одно число — результат кодирования.
Пример: для числа 2 возможно две записи: \(2 = 2^1 \cdot 1\) (запись 01) и \(2 = 2^0 \cdot 2\) (запись 2). При интерпретации чисел 01 и 2 в десятичной системе получаем суммы цифр 0+1 = 1 и 2, из них минимальна 1, значит в ответ было бы нужно записать «01».