设 $r$ 为 $(a-1{)}^n+(a+1{)}^n$ 除以 $a^2$ 的余数。

例如，如果 $a=7$ 且 $n=3$，则 $r=42$：$6^3+8^3=728\equiv 42\mathrm{mod}49$。随着 $n$ 的变化，$r$ 也会变化，但对于 $a=7$，结果是 $r_{\max }=42$。

对于 $3\le a\le 1000$，求 $\sum r_{\max }$。