b210

Vasilică tocmai a învăţat la şcoală despre sistemul de numeraţie cu baza $2$. I se pare interesant şi a inventat jocul b210, pe care vrea să îl joace cu prietenul său Gigel. Vasilică îi spune lui Gigel un număr natural nenul $n$, scris în baza $10$. Gigel trebuie să scrie numărul în baza $2$, obţinând astfel o secvenţă de cifre binare, care începe cu $1$. Asupra scrierii în baza $2$ a numărului $n$ Gigel poate aplica una sau mai multe permutări circulare. Printr-o permutare circulară, toate cifrele secvenţei date, exceptând ultima, sunt mutate cu o poziţie spre dreapta, iar ultima cifră devine prima.
De exemplu, dacă $n=107$, scrierea sa în baza $2$ este $1101011$. Prin permutări circulare succesive putem obţine, în ordine, secvenţele:

• $1110101$
• $1111010$
• $0111101$
• $1011110$

Fiecare astfel de secvenţă este scrierea în baza $2$ a unui număr natural, pe care Gigel îl transformă în baza $10$. Gigel trebuie să afle care este cel mai mare număr natural $m$, scris în baza $10$, a cărui scriere în baza $2$ se poate obţine prin una sau mai multe permutări circulare ale scrierii în baza $2$ a numărului $n$. Lui Gigel jocul nu i se pare aşa interesant şi ar prefera să aibă un program care să determine în locul lui numărul natural $m$.

Cerinţă

Scrieţi un program care citeşte numărul natural nenul $n$ şi care determină cel mai mare număr natural $m$, scris în baza $10$, care poate fi obţinut prin una sau mai multe permutări circulare ale scrierii în baza $2$ a numărului natural $n$.

Date de intrare

Fişierul de intrare b210.in conţine pe prima linie numărul natural nenul $n$.

Date de ieşire

Fişierul de ieşire b210.out va conţine pe prima linie numărul natural $m$, cu semnificaţia din enunţ.

Restricţii

• $0 < n \leq 1\ 000\ 000\ 000$

Exemplu

b210.in

13

b210.out

14

Explicație

Scrierea în baza $2$ a lui $13$ este $1101$.
Numărul maxim scris în baza $10$ a cărui scriere în baza $2$ se poate obţine din permutări circulare ale scrierii în baza $2$ a lui $13$ este $14$, care are scrierea în baza $2 \ 1110$.