I have the feeling that n power n modulo k is periodic in n, the period being a multiple of k, i.e. there exists M such that (n+Mk)^(n+Mk) = n^n modulo k. Using this fact, you can infer the distribution of n^n modulo k, without actually computing all the terms, then design an algorithm that's efficient even for a huge n (using careful combinatoric). But my math is too limited to prove the assertion and find M. A brute force approach is probably doable, as k is small (you search for a period that works for n < 10^5 and hope that it generalizes. But, frankly, I'm here to do programming, not math, so I won't pursue this route. Good luck to the braves!