Efficient Computation of the expression

Question

I have been working on a problem for quite some time now and looking for a better approach.

Problem :
You are given two integers $K$ and $N$.
For each m ($1 \le m \le N)$, you have to find the answer of the below expression

$$X=\sum_{i=1}^K i^m$$ Since answer can be large we have to return $X$ modulo $10^9+7$ for each m.

Constrainsts:
$1 \le K \lt 10^9+7 $
$1 \le N \le 10^5$

1. An obvious solution to the problem is a brute force approach of complexity $O(N*K)$.
   
2. A slightly better approach is the use of Faulhaber's forumula which would reduce the complexity to $O(N^2)$ but still is quite slower.

I am looking for a better solution. So is there a way to compute Faulhaber's formula faster or is there a different approach for the above problem?

Any sort of help is appreciated!!

Answer 1

If you look for approximations.

Using generalized harmonic numbers$$X=\sum_{i=1}^k i^m=H_k^{(-m)}$$ If $k$ is large, you can use the asymptotics $$\frac{H_k^{(-m)}-\zeta(-m)}{k^m}=\frac{k}{m+1}+\frac{1}{2}+\frac{m}{12 k}-\frac{(m-2) (m-1) m}{720 k^3}+\frac{(m-4) (m-3) (m-2) (m-1) m}{30240 k^5}+O\left(\frac{1}{k^7}\right)$$