349 : ラングトンの蟻

黒白いずれかで色づけされた正方形の規則的な格子上をアリが動く. アリは四方（上下左右）のいずれかを向いており, 次のルールに則って正方形から隣接する正方形へ動く：

• 黒い正方形上にいる場合, その正方形の色を白に変えて反時計回りに向きを変え, １マス前進する.

• 白い正方形上にいる場合, その正方形の色を黒に変えて時計回りに向きを変え, １マス前進する.

格子全体が白の状態から始めるとき, アリが $10^{18}$回動いた後の黒い正方形の数は何個あるか.