题目描述

育华学校图书馆在劳动节期间要对图书进行重新摆放。图书馆有一个特殊的书架，书架由 $n$ 层组成（$1 \leq n \leq 10^{18}$）。摆放图书有如下规则：

• 第一层可以放 $1$ 本
• 第二层可以放 $2$ 本
• 从第三层开始，每一层摆放的图书数量等于前两层摆放图书数量之和+1。

请你计算第 $n$ 层多少的图书摆放数量。由于方案数可能非常大，你需要将结果对 $10^9 + 7$ 取模。

输入格式

输入包含两个整数 $n$ ，分别表示书架的层数。

输出格式

输出一个整数，表示第 $n$ 层图书摆放数量对 $10^9 + 7$ 取模的结果。

样例

• 输入

5

• 输出

12

数据范围与提示