4 and 7

Time limit1sMemory limit128 MB

Summary
Given K, output the K-th smallest positive integer whose digits are only 4 or 7, using a binary-representation-like construction.
Level

Medium4 of 10

Topics
Math, Bit manipulation, Combinatorics
Solved
No attempts yet

Problem

Changyoung likes positive integers whose decimal representation uses only the digits 4 and 7.

List all numbers Changyoung likes in increasing order. Print the K-th number in that list.

Input

The first line contains an integer K.

  • 1 <= K <= 10^9

Output

Print the K-th smallest number among the numbers Changyoung likes.

Examples3

  1. Example 1

    Input
    1
    Expected output
    4

  2. Example 2

    Input
    2
    Expected output
    7

  3. Example 3

    Input
    3
    Expected output
    44