Find the K-th Lucky Number

A lucky number is defined as an integer whose decimal representation contains only the digits \(4\) and \(7\). This means that digits such as \(4\) and \(7\) are considered lucky, while any other digit makes the number unlucky.

For example, \(4\), \(7\), \(44\), \(47\), \(74\), and \(77\) are all lucky numbers. The task is to find the \(k\)-th lucky positive integer in sorted order (increasing order).

Hint: There are exactly \(2^n\) lucky numbers with \(n\) digits. For instance, there are 2 lucky numbers with 1 digit, 4 lucky numbers with 2 digits, 8 with 3 digits, and so on. You can first identify the length of the lucky number corresponding to \(k\), and then map the position to a binary representation, where a binary 0 corresponds to digit \(4\) and a binary 1 corresponds to digit \(7\). Ensure to use \(n\) bits for a lucky number of \(n\) digits (padding with leading zeros if necessary).

inputFormat

The input consists of a single line containing a positive integer \(k\) (\(1 \leq k \leq \text{some large number}\)).

outputFormat

Output the \(k\)-th lucky positive integer.

sample

1

4