AIME · Superchallenge problem

A sequence satisfies $a_1 = a_2 = 1$ and $a_{k+1} = 1a_k + 5a_{k-1}$ for $k \ge 2$. Find the remainder when $a_{70}$ is divided by $1000$.