说明

[md] 首先给出两个短串 A=’4567’ (4 个字符 ) ， B=’123’(3 个字符 ) 。反复进行如下的操作得到一个长串 C 。 （１） C=B+A ( 例如： A=’4567’ ,B=’123’ C=B+A=’1234567’) （２） A=B B=C ( 上述例子 A=’123’ B=’1234567’) 请你编程找出这个长串的第 n 个字符。 [/md]

输入格式

[md] 第一行包含一个整数n (1<=n<=10^9^) [/md]

输出格式

[md] 仅一行，包含一个字符，表示这个长串的第 n 个字符。 [/md]

样例

9

2

提示

[md] [/md]