2007 AIME I Problem 7

Let

N=\sum_{k=1}^{1000} k\left(\left\lceil\log _{\sqrt{2}} k\right\rceil-\left\lfloor\log _{\sqrt{2}} k\right\rfloor\right) $$ Find the remainder when $N$ is divided by 1000. (Here $\lfloor x\rfloor$ denotes the greatest integer that is less than or equal to $x$, and $\lceil x\rceil$ denotes the least integer that is greater than or equal to $x$.)