An integer $r$ is given, and the integer $N$ is up to $10^9$. Let $f_k$ the Fibonacci series starting with $f_1=f_2=1$.
How can find an algorithm which calculates the partial sum $\sum_{k=1}^{N} k^rf_k$ modular a given prime $p=10^9+7$ in the time complexity less than $O(k^2)$? It's hard to find the answer since it's not a polynomial form. Any help is appreciated.
My original problem was : Given $N, r$, calculate $\sum_{i}^{N}\sum_{j}^{N} \gcd(F_i, F_j)\gcd(i,j)^k$, didn't know something similar was in Project Euler.
Note that $h(r) = \sum_{k=1}^n k^r f_k$, then $r^2 = o(h(r))$ if $2 \leq n \leq 10^9$.
But OP says his question is actually to find an $\mathcal{O}(r^2)$ algorithm to compute $h(r)$. But clearly the vector $(1^r, 2^r, 3^r, ... , n^r)$ can be computed in $O(n \log r)$, and the vector $(F_1, F_2, F_3, ... , F_n)$ can be computed in $O(n)$, and hence $h(r)$ can be computed in $O(n \log r)$.