312 : シェルピンスキーグラフの循環路

• 1次のシェルピンスキーグラフの三角形($S_1$)は正三角形である

• $S_{n+1}$は$S_n$3つをそれぞれのペアが角の頂点を一つ共有するように配置したものである

p_312_sierpinskyAt.gif

$C(n)$を$S_n$のすべての頂点を一度だけ通るような閉路の数とする. 例えば,$S_3$については下図のように8つの閉路が描けるため$C(3) = 8$となる.

p_312_sierpinsky8t.gif

$C(1) = C(2) = 1$ $C(5) = 71328803586048$ $C(10\,000) \mod 10^8 = 37652224$ $C(10\, 000) \mod 13^8 = 617720485$ であることが確認できる.

$C(C(C(10\, 000))) \mod 13^8$を求めよ.