　一般に正 $n$ 角柱 $P_1P_2 \cdots P_n-Q_1Q_2 \cdots Q_n$ に対して考える． \
　各 $(P_i,Q_i)$ の色の組み合わせとしてありうる以下の $6$ つを，それぞれ $A,B,C,D,E,F$ とよぼう．

- （赤，青）（緑，赤）（青，緑）（青，赤）（赤，緑）（緑，青）

例えば $(P_1,Q_1)$ が $A$ であるとき， $(P_2,Q_2)$ としてありうるものは $B,C,D$ である．同様に考えると，色の組み合わせを頂点に紐づけた三角柱 $ABC-DEF$ について，$(P_i,Q_i)$ と $(P_{i+1},Q_{i+1})$ の色の組み合わせは辺でつながれた異なる二頂点に対応することがわかる．すなわち，以下の問題に帰着される：

- 三角柱 $ABC-DEF$ において，ある頂点を出発し，隣り合う頂点に移動する動作を $n$ 回行い，出発した頂点に戻る道順の数を求めよ．

　いま，$f(x,y)=(x+x^{-1}+y)^{n}$ とおき，次のような対応を考える．

- $x$：　$A \longrightarrow B, ~ B \longrightarrow C, ~ C \longrightarrow A, ~ D \longrightarrow E, ~ E \longrightarrow F, ~ F \longrightarrow D$
- $x^{-1}$：　$A \longleftarrow B, ~ B \longleftarrow C, ~ C \longleftarrow A, ~ D \longleftarrow E, ~ E \longleftarrow F, ~ F \longleftarrow D$
- $y$：　$A \longleftrightarrow D, ~ B \longleftrightarrow E, ~ C \longleftrightarrow F$

このとき，求める場合の数は $f(x,y)$ の各項のうち，$x$ の次数が $3$ の倍数かつ $y$ の次数が偶数であるものについて，その係数の総和の $6$ 倍（始点としてありうるものが $6$ つあることから）であり，$3$ 乗して $1$ になる $1$ でない複素数 $\omega$ を用いて以下のように計算できる：
$$
\begin{aligned}
X&=\dfrac{1}{6}\left(f(1,1)+f(1,-1)+f(\omega,1)+f(\omega,-1)+f(\omega^2,1)+f(\omega^2,-1)\right)\times 6 \\\\
&=3^{n}+1^n+0^n+(-2)^{n}+0^n+(-2)^{n} \\\\
&=3^{n}-(-2)^{n+1}+1
\end{aligned}
$$

$n=1234$ のときこれを $1237$ で割った余りは，Fermatの小定理により $\textbf{895}$ である．
公式解説
https://onlinemathcontest.com/contests/omc206/editorial/8554
　一般に正 $n$ 角柱 $P_1P_2…P_nQ_1Q_2…Q_n$ の塗り分けを考える．また $P_{n+1}, Q_{n+1}$ をそれぞれ $P_1, Q_1$ に塗った色と同じとし，三色の並びについて赤 $\rarr$ 青 $\rarr$ 緑 $\rarr$ 赤の順を「正の順」，赤 $\rarr$ 緑 $\rarr$ 青 $\rarr$ 赤を「負の順」と定義する．条件を満たす塗り方について，$(P_k, Q_k)$ の色と $(P_{k+1},Q_{k+1})$ の色は「正負が同じ順で色の組みが異なるもの」もしくは「正負が違う順で色の組みが同じもの」のどちらかとなる．$($ 例えば $(P_1,Q_1)=($ 赤，青 $)$ のとき $(P_2,Q_2)$ は $($ 青，緑 $)$ $($ 緑，赤 $)$ $($ 青，赤 $)$ のいずれかである $)$\
　したがって正 $n$ 角形 $A_1A_2…A_n$ の各頂点に赤，青，緑を割り振って，さらに正負を一つ定めることで「 $(P_1,Q_1)$ が定めた正負の順で，$P_k, Q_k, A_k$ が全て異なる色にする」という手順で $(P_n,Q_n)$ まで色を決定できる．この手順で $A_k$ と $A_{k+1}$ が同色の時，$(P_k,Q_k)$ と $(P_{k+1},Q_{k+1})$ は正負が違う順となるので，$(P_1,Q_1)$ と $(P_{n+1},Q_{n+1})$ が一致するためには，正 $A_1A_2…A_n$ 角形の辺で両端点の色が同一のものが偶数本である必要がある．逆に偶数本であれば条件を満たす $P_1P_2…P_nQ_1Q_2…Q_n$ の塗り分けを決定できる．以上から，「正 $n$ 角形 $A_1A_2…A_n$ の各頂点を赤，青，緑で塗り分ける方法で，両端点が同一色の辺が偶数本であるものの個数」を求めれば良い．これを $p_n$ 通りとする．\
　まず，正 $n$ 角形 $A_1A_2…A_n$ の各頂点に赤，青，緑を同一色が隣り合わないように割り振る方法を $a_n$ 通りとしてこれを求める．$a_2=6, a_3=6, a_4=18$ であり，$a_{n+2}$ は $A_{n+2}$ と $A_n$ が同一色のとき $(=a_n$ 通り $)$ ，$A_{n+1}$ の色は $2$ 通りあり，$A_{n+2}$ と $A_n$ が異なる色のとき $(=a_{n+1}$ 通り $)$ ，$A_{n+1}$ の色は $1$ 通りなので $a_{n+2}=a_{n+1}+2a_n$ となる．これを解き $a_n=2^n+2(-1)^n$ が得られる．\
　$p_{2n}$ 通りの中で両端点が同一色の辺が $2m$ 本であるものは，$a_{2n-2m}$ 通りそれぞれについて $A_1,A_2…A_{2n-2m},A_{2n-2m+1}$ から重複を許して $2m$ 個を選び「 $A_k$ が選ばれたとき辺 $A_kA_{k+1}$ 上に $A_k$ と同じ色の点を増やす，$A_{2n-2m+1}$ が選ばれたときは辺 $A_{2n-2m}A_1$ 上に $A_1$ と同じ色の点を増やす」という操作と対応させられるので
$$p_{2n}=\displaystyle\sum_{m=0}^na_{2n-2m} \times {}\_{2n-2m+1}\mathrm{H}\_{2m}= \displaystyle\sum_{m=0}^n(2^{2n-2m}+2){}\_{2n}\mathrm{C}\_{2m}=\dfrac{(2+1)^{2n}+(2-1)^{2n}}2 +((1+1)^{2n}+(1-1)^{2n})=\dfrac{3^{2n}+1}2 +2^{2n}$$
となる．これに $(P_1,Q_1)$ の順の正負を考えることで，条件を満たす塗り分けの方法は $n$ が偶数の場合 $3^n+2^{n+1}+1$ で表されることがわかる．あとは本解説と同様に求めれば良い．
やや愚直な数え上げ方での解法
https://onlinemathcontest.com/contests/omc206/editorial/8554/406
　正 $1234$ 角柱の頂点 $2468$ 個それぞれを，赤色，青色，緑色のうちから一つずつ選んで塗ります（使わない色があっても構いません）．ここで，任意の辺に対して，その両端の $2$ 頂点の色が異なるようにします．そのような塗り方が $X$ 通りあるとき，$X$ を素数 $1237$ で割った余りを求めてください．\
　ただし，回転したり裏返したりして一致する塗り方も区別して考えます．