Mock AIME 4 2006-2007 Problems/Problem 10

Problem

Compute the remainder when

${2007 \choose 0} + {2007 \choose 3} + \cdots + {2007 \choose 2007}$

is divided by 1000.

Since

$\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n$

that sum equals $2^{2007}$ . So we just need to find n such that

$n\equiv 2^{2007} \pmod {1000}$

This problem needs a solution. If you have a solution for it, please help us out by adding it.