Consider dividing the board into $1003^2$ squares of $2\times 2$. And assume the contrary. Its easy to show that each of these squares can contain at most one $4k+2$ and at most one $4k$ which means each of the squares must contain exactly one $4k$ and one $4k+2$ (otherwise we wouldn't be able to use all $1003^2$ number of the form $4k$ and $4k+2$.). On the other hand, one $2\times 2$ square cannot contain both $4k+1$ and $4k+3$ thus it must contain exactly $2$ or $0$ numbers of the form $4k+1$. But this contradicts with the fact that there are $1003^2$ (odd) numbers of the form $4k+1.$ $\square$