Most efficient way to compute $S(n, a, b) = \sum_{i=1}^n a^i i^b$?

Question

Given $n$, $a$ and $b$, find most efficient way to compute

$S(n, a, b) = \sum_{i=1}^n a^i i^b$

Most trivial way would be $O(n\cdot(n+b))$.

If we use fast exponentiation then it would be $O(n\cdot(\log n+\log b))$

I am looking for lot better, possibly all logarithmic factors.

Following up from @Integrand's comments I realised this might be the general case of any of these closed formula:

$\sum_{i=1}^ni3^i$

$\sum\limits_{i=1}^{n}ip^i$

$\sum \limits_{r=1}^d r \cdot 2^r$

But my gut feeling says there should be recurrence relation to compute Matrix exponentiation.

As brought up by @metamorphy , a,b,n are 64 bit integers and I need all the results under mod 10^9+7(ie a 32 bit prime)

Answer 1

Discarding the problem of time complexity and the modulo, for any kind of numbers $(a,b)$ $$S(n, a, b) = \sum_{i=1}^n a^i\, i^b=\text{Li}_{-b}(a)-a^{n+1}\, \Phi (a,-b,n+1)$$ where appear the polylogarithm function and the Lerch transcendent function.

For both of them, there are very efficient algorithms available.