Movie Director Shom 3

Interview

Time limit0.5sMemory limit1024 MB

Summary

Given N, print the Nth smallest number that contains at least three 6s in a row, with N up to 10^18.

Level: Medium5 of 10
Topics: Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

666 is said to be the number of the apocalypse. Many blockbuster movies therefore use titles that contain 666. Movie director Shom is the director of a series called End of the World. When George Lucas made Star Wars, he named the films Star Wars 1, Star Wars 2, up to Star Wars 6. When Peter Jackson made The Lord of the Rings, he titled the films The Lord of the Rings 1, The Lord of the Rings 2, and The Lord of the Rings 3. Shom wants to show that he surpasses Lucas and Jackson, so he decided to title his movies differently.

A doomsday number is a number that contains at least three 6s in a row. The smallest doomsday number is 666. The next largest numbers are 1666, 2666, 3666, and so on. So Shom names the first movie "End of the World 666" and the second movie "End of the World 1666". In general, the title of the Nth movie is End of the World (the Nth smallest doomsday number).

Write a program that prints the number in the title of Shom's Nth movie. Shom always makes the movies in this series in order, and he makes no other movies.

Input

The first line contains N. N is a natural number less than or equal to $10^{18}$ .

Output

Print the number in the title of the Nth movie on the first line.

Examples5

Example 1
Input
```
2
```
Expected output
```
1666
```
Example 2
Input
```
3
```
Expected output
```
2666
```
Example 3
Input
```
6
```
Expected output
```
5666
```
Example 4
Input
```
187
```
Expected output
```
66666
```
Example 5
Input
```
500
```
Expected output
```
166699
```