题目描述

斐波那契数列定义如下：

• $F_1 = 1$
• $F_2 = 1$
• $F_n = F_{n-1} + F_{n-2}$ ($n \ge 3$)

给定 $n$，求 $F_n$ 的值，对 $10^9+7$ 取模。

输入格式

输入一个整数 $n$。

输出格式

输出 $F_n$ 对 $10^9+7$ 取模的值。

样例 #1

输入

10

输出

55

数据范围

对于 $100\%$ 的数据，$1 \le n \le 10^6$。