Leet Sum

The sequence $\{a_k\}_{k=1}^{112}$ satisfies $a_1 = 1$ and $a_n = \dfrac{1337 + n}{a_{n-1}}$, for all positive integers $n$. Let

$S = \left\lfloor a_{10}a_{13} + a_{11}a_{14} + a_{12}a_{15} + \cdots + a_{109}a_{112}\right\rfloor.$

Find the remainder when $S$ is divided by $1000$.

This problem is posed by Akshaj.

Details and assumptions

The function $\lfloor x \rfloor: \mathbb{R} \rightarrow \mathbb{Z}$ refers to the greatest integer smaller than or equal to $x$. For example $\lfloor 2.3 \rfloor = 2$ and $\lfloor -5 \rfloor = -5$.