Migrated from Lutece 494 SRETAN

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Digits $4$ and $7$ are lucky, while all others are unlucky. An integer is lucky if it contains only lucky digits in decimal notation. We would like to know the $K_{th}$ lucky positive integer.

Input

The first and only line of input contains a positive integer $K$ ($1 \leq K \leq 10^9$).

Output

The first and only line of output must contain the $K_{th}$ lucky positive integer.

Samples

1

4

2

7

3

44

Resources

COCI 2010/2011, 1st round, October 23rd 2010, Author: Goran Gašić