Депутатські щасливі числа
Обмеження: 2 сек., 256 МіБ
Кожен громадянин знає, що щасливим числом є те, десятковий запис якого містить тільки четвірки та сімки. Наприклад, щасливими є числа 4, 7, 47, 7777 та 4744474.
Проте депутати — люди непересічні і їм завжди потрібно щось інакше, щось краще, щось більш вишукане чи елегантне. Вони їздять на інакших авто, вони живуть у інакших будинках. Дехто вірить, що їх навіть інопланетяни інакші викрадають.
Ця хвороблива депутатська схильність не оминула і щасливих чисел. Тож депутатським щасливим числом є таке щасливе число, у десятковому записі якого цифри змінюються щасливу кількість разів. Наприклад, депутатськими щасливими числами є 47474 та 7777477744447474, а числа 47, 47747447744777744474744774 такими не є. Число 47474 має 4 зміни цифр, число 77744 — одну зміну, а число 44444444 — жодної.
Розглянемо всі депутатські щасливі числа у порядку зростання. Ваше завдання — відшукати n-те щасливе депутатське число.
Вхідні дані
У єдиному рядку задано одне ціле число n — номер шуканого депутатського щасливого числа.
Вихідні дані
У єдиному рядку виведіть одне ціле число — n-те депутатське щасливе число.
Обмеження
1≤n≤109.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
7 | 477474 |
Примітки
Перші 7 депутатських щасливих чисел:
47474, 74747, 447474, 474474, 474744, 474774, 477474.