#6264. friend-斐波那契
题目描述
求 f12+f22+f32+....+fn2f_1^2+f_2^2+f_3^2+....+f_n^2f12+f22+f32+....+fn2 ， 其中 fif_ifi 代表斐波那契数列的第 iii 项。 (f0=0,f1=1)(f_0=0 , f_1=1)(f0=0,f1=1)
当然结果会很大，请将它对 109+710^9+7109+7 取模。
输入格式
一行一个数 nnn.
输出格式
一行一个数，代表答案。
样例
样例输入
6样例输出
104数据范围与提示
对于30%的数据：n≤105n\leq 10^5n≤105。
对于另外20%的数据: 1000000∣n1000000|n1000000∣n （即n是1000000的倍数），且n≤5∗109n\leq 5*10^9n≤5∗109。
对于100%的数据：n≤1018n\leq10^{18}n≤1018。