　各マスを頂点とし，中心が距離 $\sqrt{5}$ の関係にある $2$ マスの間に無向辺を張ったグラフ $G_n$ において，Euler路をもつ部分グラフの辺数を最大化すればよい．まず，$G_n$ の辺数 $T(n)$ について，$T(n)=4(n-1)(n-2)$ が成立することがわかる．これは，$4$ 種類の「傾き」それぞれをもつ辺について考えることで確認できる．\
　$G_3$ はすべての頂点の次数が偶数であるからEuler閉路をもつ．$n\geq 4$ に対し，$G_n$ は次数 $3$ の頂点を $8$ 個持つから，少なくとも $6$ 辺を取り除かなければ一筆書き可能とならない．ただし $G_4$ に限り，次数 $3$ の頂点どうしを結ぶ $3$ 辺を取り除けばよい．以上をまとめると，
$$M(n)=
\begin{cases}
8 && (n=3) \\\\
21 && (n=4) \\\\
2(2n^2-6n+1) && (n\geq 5)
\end{cases}$$
となる．$2(2n^2-6n+1)$ を $10$ で割った余りは $2,4,4,2,8$ と周期するから，以上により求める総和は
$$8+1+(2+4+4+2+8) \times 199= \bold {3989}$$
である．なお，$n\gt4$ において実際に $M(n) = T(n) - 6$ が成立することは，$n=7$ の場合の以下の例と同様にして左上と右上と左下の $6$ つの辺を取り除くことで，次数が奇数である頂点がちょうど $2$ 個となることから確かめられる．
![figure 1](\/images\/7jUGLO4HeD2NkWEKq7lpFmysLIkJQnek4RMMRtj0)
公式解説
https://onlinemathcontest.com/contests/omc147/editorial/3017
　$n\times n$ のマス目があります．\
　OMC君はナイトの駒を $1$ つ持っており，それを適当なマス $A_0$ に置きます．ここから，以下の条件をみたすように**ナイトの移動**をちょうど $m$ 回繰り返します：

- $k=1,\ldots,m$ について，ナイトが $k$ 回移動した時点で位置するマスを $A_k$ としたとき，$m$ 個の集合 $\\{A_0,A_1\\}, \\{A_1,A_2\\}, \ldots, \\{A_{m-1},A_m\\}$ は相異なる．

　このような移動が可能な $m$ としてありうる最大の値を $M(n)$ とおきます．\
　$n=3,4,\ldots,999$ それぞれに対して「$M(n)$ を $10$ で割った余り」を計算し，それらの総和を求めてください．
<details><summary>**ナイトの移動**について<\/summary>
　ナイトは $1$ 回の移動で，下図のように中心が距離 $\sqrt{5}$ の関係にある任意のマスに移ることができます．ただし，この過程でマス目から出てはいけません．
![figure 1](\/images\/Agvf8I8y6LHFjgehdpNFQrDXweb5Zm2f9lzNljRG)
<\/details>