HZNUOJ

斐波那契

Tags:   水题  (bm大佬说的)
Time Limit:  3 s      Memory Limit:   256 MB
Submission:116     AC:12     Score:99.35

Description

斐波那契数列的定义如下:
$\begin{cases}
F(x) = 0 \qquad (x = 0)\\
F(x) = 1  \qquad (x = 1)\\
F(x) = F(n - 1) + F(n - 2) \quad (x \ge 2)
\end{cases}$
即$F=[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...]$

给出$n$,求$(\sum{ F^2(n)+2*F(n-1)*F(n)}) \pmod{10^9+7}$

Input

输入一个数$n(1 \leq n \leq 10^{18})$

Output

输出结果

Samples

input
2
output
4

Author

JIN, SHUOWEI