Let $r$ be the remainder when $(a-1{)}^n+(a+1{)}^n$ is divided by $a^2$.

For example, if $a=7$ and $n=3$, then $r=42$: $6^3+8^3=728\equiv 42\mathrm{mod}49$. And as $n$ varies, so too will $r$, but for $a=7$ it turns out that $r_{\max }=42$.

For $3\le a\le 1000$, find $\sum r_{\max }$.