题目传送门
现在我们定义一个函数（注意在 \(n<1\) 时这个函数的值是 \(0\)）：
\[f(n)=\sum_{i=1}^n\operatorname{fib}^2(i)
\]
需要求出：
\[\sum_{i=1}^n\operatorname{fib}(i)\cdot(f(i-2)+\operatorname{fib}^2(i)+\operatorname{fib}(i))
\]
对于所有数据，\(1\le T\le 2\times 10^5\)，\(1\le n\le 10^{18}\)，\(2\le p\le 10^9+7\)。
很有意思的题
先对 \(\rm fib^2(i)\) 进行化简，裂项一下得：
\[\begin{aligned}\text{fib}^2(i)&=\left(\text{fib}(i+1)-\text{fib}(i-1)\right)\text{fib}(i))\\&=\text{fib}(i+1)\text{fib}(i)-\text{fib}(i)\text{fib}(i-1)\end{aligned}
\]
所以
\[f(n)=\sum_{i=1}^n{\text{fib}(i+1)\text{fib}(i)-\text{fib}(i)\text{fib}(i-1)=\text{fib}(n+1)\text{fib}(n)}
\]
将 \(f(i-2)\) 代入原式得：
\[\begin{aligned}&\text{fib}(i)\left(\text{fib}(i-1)\text{fib}(i-2)+\text{fib}^2(i)+\text{fib}(i)\right)\\=\:&\text{fib}(i)(\text{fib}(i-1)\text{fib}(i-2)+\text{fib}(i+1)\text{fib}(i)-\text{fib}(i)\text{fib}(i-1))+\text{fib}^2(i)\\=\:&\text{fib}(i)[\:\:\text{fib}(i+1)\text{fib}(i)-\text{fib}(i-1)(\:\text{fib}(i)-\text{fib}(i-2)\:)\:\:]+\text{fib}^2(i)\\=\:&\text{fib}(i+1)\text{fib}^2(i)-\text{fib}^2(i)\text{fib}(i-1)+\text{fib}^2(i)\end{aligned}
\]
求和得：
\[\text{fib}(n+1)\text{fib}^2(n)+\text{fib}(n+1)\text{fib}(n)
\]