题目描述

坤泽教育编程培训班的同学们在玩数数游戏，他们排成一行（一共 $10000000$人），第一个同学报数 $1$，第二个同学也报数 $1$，从第三个同学开始，每个同学报的数是前两个同学的报数之和。比如第三个同学该报数 $2$，第四个同学报数 $3$，现在排在第 $n$位的小珅同学想计算出轮到自己时该报什么数，你能帮帮他吗？

输入格式

一个数 $n$，表示小珅排在第 $n$位（$n \le 10000000$）。

输出格式

输出轮到小珅报数时他该报的数字。

10

55

提示

前 $10$个人的报数分别为 $1,1,2,3,5,8,13,21,34,55$。

数据规模与约定

对于 $100\%$的数据，$1 \le n \le 10000000$。