Hello guyz !!!

I came across this problem and I am still unable to come up with a good algorithm to solve this problem

Problem :

given, 1<=n<=1000000, and 1<=k<=9 , calculate the first and last k digits of n^n.

for example if n=13 and k=4, then

result : first 4 digits ->3028

last 4 digits ->2253

since the value of 13^13= 302875106592253

I do realize that it is not feasible to calculate the actual value of n^n, since for n=1000000, it takes up a lot of time and is not the correct method.

So, someone please suggest another suitable method to solve this.