题目描述

1202年，意大利数学家斐波那契（Fibonacci）出版了它的《计算之书》，在书中提到了一个关于兔子繁殖的问题：如
果一对兔子，过一个月之后长成大兔子，到第三个月就可以生下一对兔子并且以后每个月都生下一对兔子，而所生的一
对小兔子也同样到一个月之后长成大兔子，到第三个月就可以生下一对小兔并且以后每个月都会生一对。假如兔子都不
死，问第n个月的时候兔子的总对数为多少？

输入要求

输入一个整数n( 0 < n < =10^9)

输出要求

输出第n个月兔子的对数，由于结果可能很大，要对1000000007(10^9+7)取模。

输入样例

1000000000

输出样例

21

提示

来源