#5282. 数

内存限制:512 MiB 时间限制:10 Sec

题目描述

众所周知,萌萌哒六花不擅长数学,所以勇太给了她一些数学问题做练习,其中有一道是
这样的:
一个正整数被称为是好的当且仅当它的十进制表示是其二进制表示的后缀。
例如正整数 (100)10 就是一个好的正整数,它的二进制表示是 (1100100)2,而正整数 (2)10
就不是一个好的正整数,它的二进制表示是 (10)2。
现在勇太想要知道第 K 小的好的正整数。
当然,这个问题对于萌萌哒六花来说实在是太难了,你可以帮帮她吗

输入格式

第一行输入一个正整数 K。
K ≤ 500000。

输出格式

输出一个整数表示答案。

样例

样例输入


			
30

样例输出


			
1010000

数据范围与提示