#837. #6264. friend-斐波那契

#6264. friend-斐波那契

题目描述

求 f12+f22+f32+....+fn2f_1^2+f_2^2+f_3^2+....+f_n^2 , 其中 fif_i 代表斐波那契数列的第 ii 项。 (f0=0,f1=1)(f_0=0 , f_1=1) 当然结果会很大,请将它对 109+710^9+7 取模。

输入格式

一行一个数 nn.

输出格式

一行一个数,代表答案。

6
104

数据范围与提示

对于30%的数据:n≤105n\leq 10^5。 对于另外20%的数据: 1000000∣n1000000|n (即n是1000000的倍数),且n≤5∗109n\leq 5*10^9。 对于100%的数据:n≤1018n\leq10^{18}。