1261 - #6264. friend-斐波那契
Time Limit : 1 秒
Memory Limit : 256 MB
求 f_1^2+f_2^2+f_3^2+....+f_n^2 ， 其中 f_i 代表斐波那契数列的第 i 项。 (f_0=0 , f_1=1)
当然结果会很大，请将它对 10^9+7 取模。
Input
一行一个数 n.
Output
一行一个数，代表答案。
Examples
Input
6
Output
104
Hint
对于30\%的数据：n\leq 10^5。
对于另外20\%的数据: 1000000|n （即n是1000000的倍数），且 n\leq 5*10^9。
对于100\%的数据：n\leq10^{18}。
Source
LOJ