题目描述

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$。$(1≤n≤10^9)$

输出

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

样例

9

2

来源

字符串