　全体を，頂点が正 $3n$ 角形の頂点，辺（有向）が各頂点とその頂点から操作を一回行った時のコインの行き先の頂点を結ぶ有向グラフとみなす．このグラフが閉路を持つのは明らかであり，その閉路の大きさの最小値は $n$ であるから，条件を満たす頂点はこのときの閉路上のすべての頂点のみである． \
　従って，条件を満たす頂点は $\bmod\ 3$ で等しい頂点 $n$ 個の組でなければならず，これらの頂点にはすべて $3$ が書き込まれていることがわかる． \
　ここで上記のように頂点 $n$ 個の組からなる閉路を持ち，かつ，他にも閉路を持つとき，その閉路は頂点をちょうど $n$ 個持つ．
　<details><summary>証明<\/summary>
　まず， $n$ 個の頂点の組からなる閉路の頂点の組を $\bmod\ 3$ で $0$ と等しい $n$ 個の頂点の組としても一般性を失わない． \
　他にも $A_i(i \equiv 1\pmod3)$ を含む閉路が存在するとき，$A_i$ からのコインの行先は $A_{i+2}$ もしくは $A_{i+3}$ となるが，この閉路には，$\bmod\ 3$ で $0$ と等しい頂点を持たないから，$A_i$ からのコインの行先は $A_{i+3}$ であり，$A_{i+3}$ も閉路に属す．\
　以下，同様に繰り返すことで，この閉路の頂点の組は $\bmod\ 3$ で $1$ と等しい $n$ 個の頂点の組であることがわかる．\
　また， $A_i(i \equiv 1\pmod3)$ を含まない他の閉路が存在するとき，この閉路は $\bmod\ 3$ で $0$ と等しい頂点を持たないから，この閉路は $\bmod 3$ で $2$ と等しい $n$ 個の頂点の組からなることがわかる．\
　よって，いずれの場合も閉路を構成する頂点の個数は $n$ 個である．（証明終）
<\/details>

　ここで，長さ $n$ の閉路をちょうど二つ持つ書き込み方は $3\times2^{n}-3$ 通り，ちょうど三つ持つような書き込み方は $1$ 通りであるから
 $$ \begin{aligned} 
 a_n &=3 \times 2^{2n}-2 \times (3 \times 2^{n}-3)-3 \times 1 \\\\
 &=3 \times 4^{n}-6 \times 2^{n}+3 
 \end{aligned} $$
である．あるいは，長さ $n$ の閉路の選び方 $3$ 通りに，閉路を $1$ つずつずらした $n$ 頂点の決め方 $(2^n-1)^2$ を乗じることでも同じ表式を得る． \
　よって求めるべき値は
 $$ \begin{aligned} 
 \sum_{n=1}^{2023}a_n &=\sum_{n=1}^{2023}(3 \times 4^{n}-6 \times 2^{n}+3) \\\\
 & \equiv 3 \times \sum_{n=1}^{7}4^{n}-6 \times \sum_{n=1}^{14}2^{n}+3 \times 2023\\\\
 &=3 \times \frac{4^{8}-4}{3}-6 \times (2^{15}-2)+3 \times 2023 \\\\
 & \equiv -4+12+6069\\\\
 &=\mathbf{6077}  \pmod{2^{16}}
 \end{aligned} $$
である．
公式解説
https://onlinemathcontest.com/contests/omc182/editorial/6961
　 $n$ を正整数とします．正 $3n$ 角形 $A_1A_2A_3 \cdots\ A_ {3n} $ の各頂点に $2$ または $3$ が一つずつ書き込まれています．ただし，$A_1,A_2,A_3, \ldots\ ,A_ {3n} $ は反時計回りに並んでいるものとします．いま，ある頂点に一つコインを置いて，以下の操作を繰り返します．

- コインの置かれている頂点に $x$ が書かれているとき，反時計回りに $x$ 個隣の頂点にコインを動かす．

　以下の条件をみたす頂点がちょうど $n$ 個となるような，頂点の数字の書き込まれ方が $a_n$ 通りであるとします．

- 最初にその頂点にコインを置き，操作を十分な回数行うことによって，コインが最初に置いた頂点に戻ることができる．

　 $\sum\limits_{n=1}^{2023} a_n$ を $2^ {16} $ で割ったあまりを求めてください ．


<details><summary>コインの動かし方の例<\/summary>
　たとえば $n=2$ のとき， $A_1,A_2,A_3,A_4,A_5,A_6$ に書かれている整数がそれぞれ $2,3,2,3,2,3$ であるとすると，コインは以下のように移動します．

- 最初にコインを $A_1$ に置くと，コインは $A_1,A_3,A_5,A_1,A_3, \ldots$ のように巡回する．
- 最初にコインを $A_2$ に置くと，コインは $A_2,A_5,A_1,A_3,A_5, \ldots$ のように巡回する．
<\/details>