How to solve this problem:

PS: No editorial present for this

### You need to understand is last three digits of n^k = last three digits of ((n-1)%1000 +1 )^k.

Hence u have to find

##(1^k)%1000 to (1000^k)%1000 And store it in an array of size 1000

### And then after that add all of them(1^k to 1000^k)… And multiply it by floor(N/1000) and then add (N%1000) numbers from that array from starting (0th index) to it…

And print last three digits of it that is the answer…

#*Note:-* please use O(log(n)) approach with modulo for power function… inbuilt power function won’t work…

#### And make sure u don’t exceed long long int or int limit… (Do modulo with 1000)

#### For better understanding :-

##
Click to view

#### The reason for this soln is that… If u will see the last three digits of the series of 1^k , 2^k , … ,n^k.

### Then you will notice that it repeats after 1000 numbers

i.e last three digits of.

1^k = 1001^k ,

2^k = 1002^k ,

3^k = 1003^k (only last three digits),…

So u can only calculated those first 1000 numbers and based on them further numbers could be obtained easily…

Advice :- Try to keep everything in long long as type casting problem would give wrong answers

PS:- my personal experience