View the grid as a graph whose $112$ edges join adjacent cells. Each edge contributes its larger endpoint value positively and its smaller one negatively, so $M = \sum_v c_v a_v,$ where $a_v$ is the entry in cell $v$ and $c_v$ is the number of neighbors of $v$ with smaller entries minus the number with larger entries. Then $|c_v| \le \deg(v),$ which is $4$ for the $36$ interior cells, $3$ for the $24$ edge cells, and $2$ for the $4$ corners, and $\sum_v c_v = 0$ since each edge contributes $+1$ and $-1.$

Because $\sum_v c_v = 0,$ $$\begin{aligned} M &= \sum_v c_v \left(a_v - \tfrac{65}{2}\right) \\ &\le \sum_v \deg(v)\left|a_v - \tfrac{65}{2}\right|. \end{aligned}$$ By the rearrangement inequality this is maximized by pairing the $36$ values farthest from $\frac{65}{2}$ (namely $1$–$18$ and $47$–$64,$ whose deviations total $828$) with the interior cells, the next $24$ values ($19$–$30$ and $35$–$46,$ totaling $192$) with the edge cells, and $31$–$34$ (totaling $4$) with the corners. Hence $M \le 4 \cdot 828 + 3 \cdot 192 + 2 \cdot 4$ $= 3896.$

Equality requires every cell holding a value at most $32$ to be smaller than all its neighbors and every value at least $33$ to be larger, which a checkerboard achieves: put $1$–$32$ on the black cells ($1$–$18$ on interior blacks, $19$–$30$ on edge blacks, $31$–$32$ on black corners) and $33$–$64$ on the white cells ($33$–$34$ on corners, $35$–$46$ on edges, $47$–$64$ in the interior). Every neighbor pair then compares white over black, so $M = 3896,$ and the answer is $3896 \bmod 1000 = 896.$