Solution:

Let $S_n = a_1 + \cdots + a_n.$ We claim $2S_n = a_{n+2} + a_n,$ which holds for $n = 1$ since $2 = 1 + 1.$ If it holds for $n,$ then $$2S_{n+1} = 2S_n + 2a_{n+1} = a_{n+2} + 2a_{n+1} + a_n = a_{n+3} + a_{n+1}$$ by the recurrence, completing the induction.

Therefore $S_{28} = \frac{a_{30} + a_{28}}{2} = \frac{20603361 + 6090307}{2} = 13346834,$ whose remainder upon division by $1000$ is $834.$