algorithm - How to calculate sum of this series modulo m fast? -

so came across problem need calculate this:

1^k+(1+p)^k+(1+2*p)^k+.....+(1+n*p)^k % p

where p prime , k number strictly less p.

p less 500 , n*p range upto 10⁹

the solution think iterate first last term , calculate modulo using exponentiation costly looking faster algorithm.

is possible faster?

for integer m, (1+m*p)^k % p == 1.

thus, computing

(1^k + (1+2*p)^k  + (1+3*p)^k + ... + (1+n*p)^k )% p

is same computing

(1 + 1 + 1 ... + 1) % p

where there n + 1 terms in parentheses.

the answer (n + 1)%p.

RT