题目描述：

大家都知道，斐波那契数列是满足如下性质的一个数列：

• f(1) =1

• f(2) =1

• f(n) =f(n−1)+f(n−2) (n≥2 且 n 为整数)

输入格式：

一个正整数 n。

输出格式：

一个正整数 S，为斐波那契数列的第n项。

样例：

40

102334155

提示

对于100%的数据 0<n<46