Advanced Number Theory · Hard problem

Let $S = \displaystyle\sum_{k=1}^{100}\left\lfloor \sqrt{k} + \sqrt{k+1}\,\right\rfloor$. Find the remainder when $S$ is divided by $1000$.