help [A4]

How to find the first and the last k digits of n power n ( i.e n^n).

Constraints:

1 ≤ n ≤ 10^9, 1 ≤ k ≤ 9

k is not more than the number of digits of n^n..

please help. I googled it a lot, but couldn’t find any solution(s).

Well, the most straightforward answer would be:
to find the first k digits, divide n^n by 10^(# of digits of n^n - k), integer division.
and to find the last k digits, find the result of n^n % k.

But i think it would result in TLE.

One tricky situation is, for example when n is 10, then the last k digits would be 0’s with the length of k (if k < # of digits of n^n). Or maybe it would be just one 0? Don’t know yet. xD

//