When the expression $\left[(1+x)\left(1+2 x^{3}\right)\left(1+4 x^{9}\right)\left(1+8 x^{27}\right)\left(1+16 x^{81}\right)\left(1+32 x^{243}\right)\left(1+64 x^{729}\right)\right]^{2}$ is expanded and simplified, the coefficient of $x^{2003}$ is
(A) 0
(B) $2^{28}$
(C) $2^{30}$
(D) $2^{29}$
(E) $2^{31}$
We first of all rewrite the given expression as

$$
\begin{aligned}
& {\left[(1+x)\left(1+2 x^{3}\right)\left(1+4 x^{9}\right)\left(1+8 x^{27}\right)\left(1+16 x^{81}\right)\left(1+32 x^{243}\right)\left(1+64 x^{729}\right)\right]^{2}} \\
& =\left(1+2^{0} x^{3^{0}}\right)^{2}\left(1+2^{1} x^{3^{1}}\right)^{2}\left(1+2^{2} x^{3^{2}}\right)^{2}\left(1+2^{3} x^{3^{3}}\right)^{2}\left(1+2^{4} x^{3^{4}}\right)^{2}\left(1+2^{5} x^{3^{5}}\right)^{2}\left(1+2^{6} x^{3^{6}}\right)^{2}
\end{aligned}
$$

We note that $\left(1+2^{r} x^{3^{r}}\right)^{2}=1+2^{r} x^{3^{r}}+2^{r} x^{3^{r}}+2^{2 r} x^{2 \cdot 3^{r}}$, so each of the four terms in this expansion has the form $2^{m r} x^{m 3^{r}}$ where $m$ is 0,1 or 2 .

When we multiply the expansions of the seven factors, each of the four terms in each expansion will be multiplied by each of the four terms in each other expansion.

So when this complicated-looking expression is multiplied out, every term is of the form

$$
2^{0 a+1 b+2 c+3 d+4 e+5 f+6 g} x^{a 3^{0}+b 3^{1}+c 3^{2}+d 3^{3}+e 3^{4}+f 3^{5}+g 3^{6}}
$$

where the values of $a, b, c, d, e, f, g$ can each be $0,1,2$, telling us to take the first term, one of the middle terms, or the last term, respectively.

Since we are looking for the coefficient of $x^{2003}$, we need to look at the equation $a 3^{0}+b 3^{1}+c 3^{2}+d 3^{3}+e 3^{4}+f 3^{5}+g 3^{6}=2003$

where each of the coefficients can be 0,1 or 2 .

Let's look first at the value of $g$. Could $g$ be 0 or 1 ? If this is the case then the largest possible value of the left side $2 \cdot 3^{0}+2 \cdot 3^{1}+2 \cdot 3^{2}+2 \cdot 3^{3}+2 \cdot 3^{4}+2 \cdot 3^{5}+3^{6}=1457$.

But this is too small, so $g=2$.

Substituting and simplifying, we get $a 3^{0}+b 3^{1}+c 3^{2}+d 3^{3}+e 3^{4}+f 3^{5}=545$.

Next, we look at the value of $f$. If $f$ was 0 or 1 , then

$a 3^{0}+b 3^{1}+c 3^{2}+d 3^{3}+e 3^{4}+f 3^{5} \leq 2 \cdot 3^{0}+2 \cdot 3^{1}+2 \cdot 3^{2}+2 \cdot 3^{3}+2 \cdot 3^{4}+3^{5}=485$ So $f=2$.

In a similar fashion, we can determine that $e=0, d=2, c=0, b=1$, and $a=2$.

These values are uniquely determined.

[Alternatively, we could notice that the equation

$$
a 3^{0}+b 3^{1}+c 3^{2}+d 3^{3}+e 3^{4}+f 3^{5}+g 3^{6}=2003
$$

is asking for the base 3 expansion of 2003, which we could calculate as 2202012, thus obtaining the same result.]

So each term containing $x^{2003}$ is of the form

$$
2^{0(2)+1(1)+2(0)+3(2)+4(0)+5(2)+6(2)} x^{2003}=2^{29} x^{2003} \text {. }
$$

To determine the coefficient of $x^{2003}$, we need to determine the number of terms of the form $2^{29} x^{2003}$ that occur before we simplify the expansion.

We note that each term of the form $2^{29} x^{2003}$ has a contribution of one term from each of the seven factors of the form $\left(1+2^{r} x^{3^{r}}+2^{r} x^{3^{r}}+2^{2 r} x^{2 \cdot 3^{r}}\right)$.

Since $a=2$, the expansion $1+x+x+x^{2}$ of $(1+x)^{2}$ contributes the term $x^{2}$ to the product. Similarly, since $d=2, f=2$, and $g=2$, the expansions of $\left(1+2^{3} x^{3^{3}}\right)^{2}$, $\left(1+2^{5} x^{3^{5}}\right)^{2}$ and $\left(1+2^{6} x^{3^{6}}\right)^{2}$ each contribute their last term.

Since $c=0$ and $e=0$, the expansions of $\left(1+2^{2} x^{3^{2}}\right)^{2}$ and $\left(1+2^{4} x^{3^{4}}\right)^{2}$ each contribute their first term, namely 1 .

Since $b=1$, the expansion of $\left(1+2^{1} x^{3^{1}}\right)^{2}$ contributes the two middle terms $2^{1} x^{3^{1}}$ and $2^{1} x^{3^{1}}$. There are thus two terms of the form $2^{29} x^{2003}$ in the product, and so their sum is $2 \cdot 2^{29} x^{2003}=2^{30} x^{2003}$.

The coefficient of $x^{2003}$ is $2^{30}$.