Solution:

Since $\binom{n}{2} = \frac{n(n-1)}{2}$ and $\binom{n}{2} - 1 = \frac{(n+1)(n-2)}{2},$ $$\binom{\binom{n}{2}}{2} = \frac{1}{2} \cdot \frac{n(n-1)}{2} \cdot \frac{(n+1)(n-2)}{2} = \frac{(n+1)n(n-1)(n-2)}{8} = 3\binom{n+1}{4}.$$

By the hockey stick identity, $$\sum_{n=3}^{40} 3\binom{n+1}{4} = 3\sum_{k=4}^{41}\binom{k}{4} = 3\binom{42}{5} = 3 \cdot 850668 = 2552004.$$

The remainder upon division by $1000$ is $4.$