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

1216: #6264. friend-斐波那契

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

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^5n105

对于另外20%的数据: 1000000∣n1000000|n1000000n (即n是1000000的倍数),且n≤5∗109n\leq 5*10^9n5109

对于100%的数据:n≤1018n\leq10^{18}n1018

Source/Category