题目描述

小华养了一对兔子，它们每个月生一对小兔子。每对小兔子从第三个月开始也能每月生一对。假设所有兔子都不死，且兔子的繁殖满足如下规律：

$$F_n = \begin{cases} 1 & (n \le 2) \\ F_{n-1} + F_{n-2} & (n \ge 3) \end{cases}$$

其中 $F_n$ 表示第 $n$ 个月的兔子对数。请你求出 $F_n \bmod (10^9 + 7)$ 的值。

输入格式

一行一个正整数 $n$。

输出格式

输出一行一个整数，表示 $F_n \bmod (10^9 + 7)$ 的值。

样例

5

5

10

55

提示

数据范围

对于 $60\%$ 的数据，$1 \le n \le 92$。

对于 $100\%$ 的数据，$1 \le n \lt 2^{63}$。