题目描述

先去做 p0216 斐波那契数列 l

斐波那契数列是一个经典的数学序列，它的定义如下：从第三项开始，每一项都等于前两项之和；

斐波那契数列: $1$ $1$ $2$ $3$ $5$ $8$ $...$

输入格式

共一行，输入一个正整数 $n$。

输出格式

在一行中输出斐波那契数列的第 $n$ 项对 $1e9 + 7$ 取余的结果；

数据范围

$1 \leq n \leq 10^6.$

输入样例：

6

输出样例：

8