斐波那契数列2

题目描述

斐波那契数列指的是以下数列: $1, 1, 2, 3, 5, 8, ...$，从第三个数开始，每个数是前两个数的和。

请问这个数列的第 $n$ 项模 $10^9 + 7$ 是多少。

输入格式

第一行一个整数 $n$。

输出格式

一行一个数表示答案。

样例输入

5

样例输出

5

数据范围

对于 $100\%$ 的数据，保证 $1\leq n\leq 10^9$。