The answer is $601200=\frac35(1001^2-1)$ First, we show that among any five consecutive squares in a row or column, at least three are marked. Case 1: Two consecutive squares in the block of five are marked. Then, since at least two of the other three are adjacent to each other, at least one of them is marked. Case 2: No two consecutive squares in the block are marked. Then the markings form one of these two patterns: M_M_M or _M_M_. The first pattern has three marked squares, so we are done in that case. In the second case, we can form a block of six including those five, which then has the pattern _M_M_?. Whether the ? is marked or not, this block has no adjacent marked squares, contradicting the rules of the construction and making this case impossible. Now, we can partition all but one corner square of the array into $5\times 1$ or $1\times 5$ blocks by first dividing into rectangles $1001\times 1000$, $1000\times 1$, and $1\times 1$. This establishes $\frac35(1001^2-1)$ as a minimum. To achieve this minimum, we need an explicit construction: Let the squares be represented by ordered pairs of integers $(m,n)$ with $0\le m,n \le 1000$. Mark $(m,n)$ if $m+n \equiv 1$ or $3$ or $4$ mod $5$. This obviously is a valid marking; the sum $m+n$ ranges over consecutive integers in any $k\times 1$ or $1\times k$ block. Also, every $5\times 1$ or $1\times 5$ block has exactly 3 marked squares. To count the number of marked squares, we divide all but the square $(0,0)$ into nonoverlapping $5\times 1$ or $1\times 5$ blocks; each small block has 3 marked squares for a total of $601200$ and the corner is not marked.

I did it similary but with other numbers mod 5