斐波那契

斐波那契

题号：NC200184
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$Keven$ 特别喜欢斐波那契数列，已知 $fib_1=1$ ， $fib_2=1$ ，对于 $n>=3$ ， $fib_{n}=fib_{n-2}+fib_{n-1}$ ，并且他想知道斐波那契前 $n$ 项平方和是多少？

为了防止答案过大，请将最后的答案模 $1e9+7$

输入描述:

第一行一个整数 $n$ （ $1<=n<=1e18$ ）

输出描述:

在一行中输出斐波那契数列的前 $n$ 项平方和模 $1e9+7$

示例1

输入

复制

输出

复制

说明