China Hong Kong Mathematical Olympiad

Firstly, since $2^{2006} < 10^{2006}$, we have
$$f(2^{2006}) \le (9 \times 2006)^2 < 10^{10}.$$
Secondly, this implies
$$f_2(2^{2006}) \le (9 \times 10)^2 = 8100.$$
Similarly, we find that
$$f_3(2^{2006}) \le (7 + 9 + 9 + 9)^2 = 1156$$
and
$$f_4(2^{2006}) \le (9 \times 3)^2 = 729.$$
It follows that the sum of digits of $f_k(2^{2006})$ cannot exceed 27 for $k \ge 4$.
Next, since $2^6 \equiv 1 \pmod 9$ and $2006 \equiv 2 \pmod 6$, we have
$$2^{2006} \equiv 2^2 \equiv 4 \pmod 9.$$
We easily find that $f_k(2^{2006}) \equiv 7 \pmod 9$ for odd $k$ and $f_k(2^{2006}) \equiv 4 \pmod 9$ for even $k$. Thus, the sum of digits of $f_{2005}(2^{2006})$ can only be 7, 16, 25. This yields $f_{2006}(2^{2006}) = 49, 256, 625$ and hence $f_{2007}(2^{2006}) = 169.