Advanced Number Theory · Challenge problem

A sequence is defined by $a_1 = 1$, $a_2 = 1$, and $a_{n+2} = a_{n+1} + 2a_n$. Find the remainder when $a_{30}$ is divided by $1000$.