Movie Director Shom

Time limit2sMemory limit128 MB

Summary

Find the N-th smallest positive integer whose decimal digits contain at least three consecutive 6s, for N up to 10000.

Level: Medium6 of 10
Topics: Binary search, Dynamic programming, Math, String
Solved: No attempts yet

Problem

The number 666 is said to symbolize the end of the world, so many blockbuster movies use 666 in their titles.

Movie director Shom is making a film series called End of the World. Instead of numbering the titles with 1, 2, 3, and so on like other directors, Shom decides to use his own rule.

A doom number is a positive integer whose decimal representation contains at least three consecutive 6s. The smallest doom number is 666, followed by 1666, 2666, 3666, ... .

Shom uses 666 in the title of the first movie and 1666 in the title of the second movie. In general, the N-th movie title contains the N-th smallest doom number.

Given N, write a program that prints the number used in the title of Shom's N-th movie. Shom always makes the movies in order and does not make any other movies.

Input

The first line contains a positive integer N. N is at most 10,000.

Output

Print the N-th smallest doom number 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
```