题目描述

满足以下条件的正整数称为“好整数”：

选择 $2$ 的幂（$1,2,4,8,16,\dots$）中的一个或多个（允许重复，也允许改变顺序），将它们作为字符串拼接起来，再将得到的字符串解释为整数，即可得到该数。

请找出第 $N$ 小的好整数。
保证第 $N$ 小的好整数不超过 $10^9$。

输入格式

输入一个数 $N$

输出格式

输出一个数，第 $N$ 小的好整数

输入输出样例 #1

输入 #1

10

输出 #1

21

输入输出样例 #2

输入 #2

69

输出 #2

328

输入输出样例 #3

输入 #3

1099898

输出 #3

819264512

说明/提示

约束

• $N$ 是正整数。
• 第 $N$ 小的好整数不超过 $10^9$。