HINT for summing digits of a large power I recently started working through the Project Euler challenges, but I've got stuck on #16 (http://projecteuler.net/problem=16)

$2^{15} = 32768$ and the sum of its digits is $3 + 2 + 7 + 6 + 8 = 26$. What is the sum of the digits of the number $2^{1000}$?

(since I'm a big fan of generality, my interpretation is to find a solution to the sum of digits of $a^b$ in base $c$, and obviously I'm trying to solve it without resorting to "cheats" like arbitrary-precision numbers).
I guess this is simpler than I'm making it, but I've got no interest in being told the answer so I haven't been able to do a lot of internet searching (too many places just give these things away). So I'd appreciate a hint in the right direction.
I know that $2^{1000} = 2^{2*2*2*5*5*5} = (((((2^2)^2)^2)^5)^5)^5$, and that the repeated sum of digits of powers of 2 follows the pattern $2, 4, 8, 7, 5, 1$, and that the last digit can be determined by an efficient pow-mod algorithm (which I already have from an earlier challenge), but I haven't been able to get further than that… (and I'm not even sure that those are relevant).

Just note that no problem in Project Euler requires you to use bigger numbers than $2^{64}-1$ (or $2^{63}-1$ for signed). However sometimes it is just too painful to avoid big numbers, so it is just easier to use them. 
That being said, I don't think there is a mathematical trick for this problem, although I think the problem really just asks you to implement your own multiplication in terms of base $10$ digits. You know already how to do that on paper! Try $2\cdot 2$, $4 \cdot 2$, $8 \cdot 2$, $\dots$ by hand, notice how digits are carried over. Try to formalize this into an algorithm that uses array for digits. Test it for small values, then use it for $2^{1000}$ (just repeat $1000$ times). Finally it is only about the sum.
It might feel a bit unsatisfactory that all you are required to do is multiplication, but hey, it is just $16$-th problem yet!
