How to calculate the sum of this series modulo m quickly?

Question

so I ran into this problem when I need to calculate this:

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

Where p is prime and k is a number strictly less than p.

p is less than 500, and n * p can be in the range of up to 10 ⁹

The only solution I could think of is to iterate from the first to the last term and calculate the module using exponential, but that would be too expensive. I am looking for a faster algorithm.

Is it possible to do it faster?

Answer 1

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

,

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

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

n + 1.

, (n + 1)%p.