OMC182(C)

点数: 300

Writer: imabc

　 $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}$ で割ったあまりを求めてください ．