#6264. friend-斐波那契

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

求 $f_1^2+f_2^2+f_3^2+....+f_n^2$ ，其中 $f_i$ 代表斐波那契数列的第 $i$ 项。 $(f_0=0 , f_1=1)$

当然结果会很大，请将它对 $10^9+7$ 取模。

一行一个数 $n$ .

一行一个数，代表答案。

输入

输出

对于 $30\%$ 的数据， $n\leq 10^5$ 。
对于另外 $20\%$ 的数据， $n$ 是 $10^6$ 的倍数，且 $n\leq 5×10^9$ 。
对于 $100\%$ 的数据， $n\leq10^{18}$ 。