题目描述
九连环是中国民间玩具。规定环在杆上用1表示,环在下面用0表示。规定最左边的环是可以任意上下的那一环,输出数据中最右边必须是1,也就是说,010100要写成0101。
现在是X连环,由于“输出数据中最右边必须是1” ,所以X可以理解为无限大,右边多余的0在输出时都省略。初始化各环都是0,以下是前9步的情况:
1 1
2 11
3 01
4 011
5 111
6 101
7 001
8 0011
9 1011
问在X连环装上过程中,第n步完成后,具体情况是怎么样的。
输入格式
一个数N(0<N<2^63)
输出格式
X连环的具体情况,规定最左边的环是可以任意上下的那一环,最右边必须是1,数据之间没有空格.
样例输入
样例输出