8. [6] For each positive integer $n$ and non-negative integer $k$, define $W(n, k)$ recursively by
$$
W(n, k)=\left\{\begin{array}{ll}
n^{n} & k=0 \\
W(W(n, k-1), k-1) & k>0 .
\end{array}\right.
$$

Find the last three digits in the decimal representation of $W(555,2)$.
Answer:
875

For any $n$, we have
$$
W(n, 1)=W(W(n, 0), 0)=\left(n^{n}\right)^{n^{n}}=n^{n^{n+1}} .
$$

Thus,
$$
W(555,1)=555^{555^{556}} .
$$

Let $N=W(555,1)$ for brevity, and note that $N \equiv 0(\bmod 125)$, and $N \equiv 3(\bmod 8)$. Then,
$$
W(555,2)=W(N, 1)=N^{N^{N+1}}
$$
is $0(\bmod 125)$ and $3(\bmod 8)$.
From this we can conclude (by the Chinese Remainder Theorem) that the answer is 875 .