题目描述

九连环是由九个彼此套接的圆环和一根横杆组成，九个环从左到右依次为 1 ~ 9，每个环有两种状态：1 和 0，1 表示环在杆上，0 表示环不在杆上。

初始状态是九个环都在杆上，即：111111111，目标状态是九个环都不在杆上，即：000000000，由初始状态到目标状态的变化规则是：

1. 第一环为无论何时均可自由上下横行。

2. 第二只环只有在第一环为 1 时，才能自由上下。

3. 想要改变第 n（n ＞ 2）个环的状态，需要先使第 1 到第 n - 2 环均为下杆，且第 n - 1 个环为上杆，而与第 N + 1 个到第 9 环状态无关。

4. 每改变一个环，记为一步。

现在九连环由 111111111 变到000000000，求中间第 i 步的状态

输入格式

一个整数 i。

输出格式

仅包含中间第 i 步的状态。如果输入的步数大于实际变换所需的步数，则输出 -1。

样例

2

010111111