Saudi Arabian Mathematical Competitions

First, by induction, one can show that
$$S = \binom{n}{0} a_{0} + \binom{n}{1} a_{1} + \cdots + \binom{n}{n} a_{n}$$
if the Pascal triangle consists of $n$ rows.

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

Claim 1. $\binom{2p}{p} \equiv 2 \pmod{p}$.
Indeed,
$$\begin{aligned} & \binom{2p}{p} - 2 = \frac{(2p)!}{p!p!} - 2 = \frac{(p+1)(p+2) \ldots (2p-1)(2p)}{p!} - 2 \\ & = 2 \frac{(p+1)(p+2) \ldots (2p-1) - (p-1)!}{(p-1)!} \end{aligned}$$
The numerator is congruent to $1 \cdot 2 \cdot 3 \cdot (p-1) - (p-1)! = 0 \pmod{p}$ so $\binom{2p}{p} \equiv 2 \pmod{p}$.

Claim 2. $\binom{2p}{k} \equiv 0 \pmod{p}$ for $1 \leq k \leq 2p-1$ and $k \neq p$.
Indeed,
Since $\binom{2p}{k} = \binom{2p}{2p-k}$ so we can suppose $1 \leq k < p$. Similar calculation, we have
$$\binom{2p}{k} = \frac{(2p-k+1)(2p-k+2) \ldots (2p-1)(2p)}{k!}.$$
The numerator is divisible by $p$ while $(p, k!) = 1$ since $1 \leq k < p$ so we are done.

From this, we can conclude that, if $1009 \mid S$ then $a_{0} + a_{2018} + 2 a_{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}$.