第一步：把$a_{n+3} = a_{n+2} + a_{n+1} + a_n$代入$n = 1, 2, 3, \ldots, 27$，得：

$$\begin{aligned} a_4 &= a_3+a_2+a_1, \\ a_5&=a_4+a_3+a_2, \\ a_6&=a_5+a_4+a_3, \\\vdots \\ a_{30}&=a_{29}+a_{28}+a_{27}. \end{aligned}$$

第二步：令$S = a_1 + a_2 + \ldots + a_{28}$（即所求的量）。将这些等式全部相加，发现等式左边与右边分别等于

$$S + a_{29} + a_{30} - a_1 - a_2 - a_3 = (S + a_{29} - a_1-a_2) + (S - a_1) + (S-a_{28}).$$

第三步：化简并解出$S$，得到

$$S = \frac{a_{28} + a_{30}}{2} = \frac{6090307+20603361}{2} = \frac{\dots 3668}{2} = \dots 834.$$

第四步：因此，$S$除以$1000$的余数是$\boxed{834}$。