Digital Evolution Foundation#12825

Digital Evolution Foundation

1 секунда
512 мегабайтів
Складна

Фундація Цифрової Еволюції нарешті вирішила надати кожній людині у Галактиці ідентифікаційний номер.

Кожен номер є 15-ти цифровим цілим числом. Перша цифра не може бути нулем. Однак, у числі є принаймні один нуль, але два нулі не йдуть послідовно.

Усі можливі числа записані у порядку зростання та видаються людям у порядку надходження запитів від них. Але деякі люди з далечин галактики запізнились з реєстрацією і зараз хвилюються що у Фундації можуть закінчитись для них номери.

Чи можете ви знайти число надане -й людині що надіслала запит або сказати що усі номери уже роздали?

Вхідні дані

Перший рядок містить одне ціле (1 \leq n \leq 10^{16}).

Вихідні дані

Надрукуйте 15-ти цифрове число що видали -й людині. Якщо такого числа немає, надрукуйте .

Приклади

Приклад 1

Loading
Loading