问题描述

具体描述见教材p153：九连环是由九个彼此套接的圆环和一根横杆组成，九个环从左到右依次为1~9，每个环有两种状态：1和0，1表示环在杆上， 0表示环不在杆上。初始状态是九个环都在杆上，即111111111, 目标状态是九个环都不在杆上，即000000000，由初始状态到目标状态的变量规则是： (1) 第一环为无论何时均可自由上下横杆。 (2) 第二只环只有在第一环为1时，才能自由上下。 (3) 想要改变n(n>2)个环的状态，需要先使第1到第(n-2)环均为下杆，且第n-1个环为上杆，而与第n+1个第九环的状态无环。 (4) 每改变一个环，记为一步。 现在九连环由111111111变到000000000，求中间第i步的状态。

格式

输入

仅包含一个整数i。

输出

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

样例

2

010111111

500

-1

限制

1s, 64MB.