Deputy Lucky Numbers

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Every citizen knows that a lucky number is one whose decimal representation contains only fours and sevens. For example, 4, 7, 47, 7777, and 4744474 are lucky numbers.

However, deputies are extraordinary people, and they always need something different, something better, more refined, or elegant. They drive different cars, they live in different houses. Some believe that even different aliens kidnap them.

This morbid deputy propensity did not bypass lucky numbers either. Thus, a deputy lucky number is such a lucky number in whose decimal representation the digits change a lucky number of times. For example, 47474 and 7777477744447474 are deputy lucky numbers, while 47, 47747447744777744474744774 are not. The number 47474 has 4 digit changes, the number 77744 has one change, and the number 44444444 has none.

Let’s consider all deputy lucky numbers in ascending order. Your task is to find the \(n\)-th deputy lucky number.

Input

The single line contains a single integer \(n\) — the index of the desired deputy lucky number.

Output

In the single line, output a single integer — the \(n\)-th deputy lucky number.

Constraints

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

Samples

Input (stdin) сopy	Output (stdout) сopy
7	477474

Notes

The first 7 deputy lucky numbers:

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