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 \leq n \leq 10^8）。

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

字符串

字符串