题目描述

九连环是由九个彼此套接的圆环和一根横杆组成，九个环从左到右依次为 1~9 ，每个环有两种状态： 1 和 0 , 1 表示环在杆上， 0 表示环不在杆上。初始状态是九个环都在杆上，即： 111111111 ，目标状态是九个环都不在环上，即: 000000000 ，由初始状态到目标状态的变化规则是：

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

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

3. 想要改变第 n ( n > 2 )个环的状态，需要先使第一到第( n - 2 )环均为下杆，且第 n-1 个环为上杆，而与第 n+1 个到第九环状态无关。

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

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

输入格式

一个整数 i。

输出格式

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

样例

2

010111111

500

-1