I know how to come up with $F(n, k) = \sum \limits_{p=1}^n p^k$ recursively knowing $F(n, k-1)$.
But what if I want to find it in a very short time?
I know how to find fast $f_n = \sum\limits_{i=1}^{n-1} a_i f_i$, where $(a_1, ..., a_{n-1})$ are constants. It can be achieved using matrix multiplication in logarithmic time. I've heard that it is possible to solve this problem using similar method but I don't know how.
Note: For simplicity it is fine to get just F(n,k) modulo some prime number say $10^9+7$