说明

fish在无数次oi竞赛的狱炼之后，悟出一个真理，往往越容易的题目，陷阱越深。由此，fish创作了这道题目。

fish首先给出两个短串A=’4567’ (4个字符)， B=’123’(3个字符)。反复进行如下的操作得到一个长串C。

(1) C=B+A

例如：A=’4567’ ,B=’123’ C=B+A=’1234567’

(2) A=B B=C

上述例子 A=’123’ B=’1234567’

请你编程找出这个长串的第$n$个字符。

输入格式

第一行包含一个整数 $n$

输出格式

仅一行，包含一个字符，表示这个长串的第$n$个字符。

样例

9

2

数据范围

$1\leqslant n\leqslant 10^9$