so I came across this problem where I need to calculate this:
1k+(1+p)k+(1+2*p)k+.....+(1+n*p)k % p
Where p is prime and k is some number strictly less than p.
p is less than 500 and n*p could range upto 109
The only solution I could think is iterate from first to last term and calculate the modulo using exponentiation but that would be too costly I am looking for a faster algorithm.
Is it possible to do it faster?