Фундація Цифрової Еволюції нарешті вирішила надати кожній людині у Галактиці ідентифікаційний номер.
Кожен номер є 15-ти цифровим цілим числом. Перша цифра не може бути нулем. Однак, у числі є принаймні один нуль, але два нулі не йдуть послідовно.
Усі можливі числа записані у порядку зростання та видаються людям у порядку надходження запитів від них. Але деякі люди з далечин галактики запізнились з реєстрацією і зараз хвилюються що у Фундації можуть закінчитись для них номери.
Чи можете ви знайти число надане -й людині що надіслала запит або сказати що усі номери уже роздали?
Перший рядок містить одне ціле (1 \leq n \leq 10^{16}).
Надрукуйте 15-ти цифрове число що видали -й людині. Якщо такого числа немає, надрукуйте .
Приклад 1