题目背景

斐波那契数列，又称黄金分割数列或兔子数列。它的前面几项是这样的：

1 1 2 3 5 8 13 21 34 55 89 144

它的递推公式为 $\text{第n项}~f(n)=f(n-2)+f(n-1)$，其中 $f(1)=f(2)=1$，我们可以用线性的时间复杂度计算出斐波那契数列的第 $n$ 项。

题目描述

给你一个数 $n$，请你求斐波那契数列第 $n$ 项，答案对 $10^9+7$ 取模。

输入格式

一行，一个数 $n$。

输出格式

一行，斐波那契数列第 $n$ 项 $\bmod 10^9+7$ 的值。

输入输出样例

3

2

数据范围

对于 $20\%$ 的数据： $1\le n\le30$；

对于 $60\%$ 的数据： $1\le n\le10^8$；

对于 $100\%$ 的数据： $1\le n\le10^{15}$；