Депутатські щасливі числа

Обмеження: 2 сек., 256 МіБ

Кожен громадянин знає, що щасливим числом є те, десятковий запис якого містить тільки четвірки та сімки. Наприклад, щасливими є числа 4, 7, 47, 7777 та 4744474.

Проте депутати — люди непересічні і їм завжди потрібно щось інакше, щось краще, щось більш вишукане чи елегантне. Вони їздять на інакших авто, вони живуть у інакших будинках. Дехто вірить, що їх навіть інопланетяни інакші викрадають.

Ця хвороблива депутатська схильність не оминула і щасливих чисел. Тож депутатським щасливим числом є таке щасливе число, у десятковому записі якого цифри змінюються щасливу кількість разів. Наприклад, депутатськими щасливими числами є 47474 та 7777477744447474, а числа 47, 47747447744777744474744774 такими не є. Число 47474 має 4 зміни цифр, число 77744 — одну зміну, а число 44444444 — жодної.

Розглянемо всі депутатські щасливі числа у порядку зростання. Ваше завдання — відшукати \(n\)-те щасливе депутатське число.

Вхідні дані

У єдиному рядку задано одне ціле число \(n\) — номер шуканого депутатського щасливого числа.

Вихідні дані

У єдиному рядку виведіть одне ціле число — \(n\)-те депутатське щасливе число.

Обмеження

\(1 \le n \le 10^9\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7	477474

Примітки

Перші 7 депутатських щасливих чисел:

47474, 74747, 447474, 474474, 474744, 474774, 477474.