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?
The first line contains the only integer (1 \leq n \leq 10^{16}).
Print a 15-digit identification number given to the -th person. If there is no such number, print .
Example 1