Digital Evolution Foundation#12825

Digital Evolution Foundation

1 second
512 megabytes
Hard

The Digital Evolution Foundation finally decided to give each person in the Galaxy an identification number.

Each number is a 15-digit integer. The first digit is not a zero. However, there is at least one zero, but there are no two consecutive zeros.

All possible numbers are written down in increasing order and are given to people in the order they sent a request. But some people from the galaxy far far away were too late to register and now they are worrying that the Foundation is out of the numbers.

Can you find out the number assigned to the -th person who asked about it or tell that all correct numbers are already given out?

Input

The first line contains the only integer (1 \leq n \leq 10^{16}).

Output

Print a 15-digit identification number given to the -th person. If there is no such number, print .

Examples

Example 1

Loading
Loading