SAUDI ARABIAN MATHEMATICAL COMPETITIONS

First, by induction, one can show that $$S=\left(\genfrac{}{}{0ex}{}{n}{0}\right)a_0+\left(\genfrac{}{}{0ex}{}{n}{1}\right)a_1+\cdots +\left(\genfrac{}{}{0ex}{}{n}{n}\right)a_n$$ if the Pascal triangle consists of $n$ rows.

Note that for any odd prime $p$, we also have:

Claim 1. $\left(\genfrac{}{}{0ex}{}{2p}{p}\right)\equiv 2(\mathrm{mod}p)$. Indeed, $$\begin{array}{rl}& \left(\genfrac{}{}{0ex}{}{2p}{p}\right)-2=\frac{(2p)!}{p!p!}-2=\frac{(p+1)(p+2)\dots (2p-1)(2p)}{p!}-2\\ & =2\frac{(p+1)(p+2)\dots (2p-1)-(p-1)!}{(p-1)!}\end{array}$$ The numerator is congruent to $1\cdot 2\cdot 3\cdot (p-1)-(p-1)!=0(\mathrm{mod}p)$ so $\left(\genfrac{}{}{0ex}{}{2p}{p}\right)\equiv 2(\mathrm{mod}p)$.

Claim 2. $\left(\genfrac{}{}{0ex}{}{2p}{k}\right)\equiv 0(\mathrm{mod}p)$ for $1\le k\le 2p-1$ and $k\ne p$. Indeed, Since $\left(\genfrac{}{}{0ex}{}{2p}{k}\right)=\left(\genfrac{}{}{0ex}{}{2p}{2p-k}\right)$ so we can suppose $1\le k<p$. Similar calculation, we have $$\left(\genfrac{}{}{0ex}{}{2p}{k}\right)=\frac{(2p-k+1)(2p-k+2)\dots (2p-1)(2p)}{k!}.$$ The numerator is divisible by $p$ while $(p,k!)=1$ since $1\le k<p$ so we are done.

From this, we can conclude that, if $1009\mid S$ then $a_0+a_{2018}+2a_{1009}$ is divisible by $1009$. This only happens when all of them are equal to $0$.

The other numbers can be assigned any of $0$ or $1$ so the number of ways is $2^{2016}$.