　 $a_1=2,a_2=40$ である．以下，$n\geq 3$ とする．\
正 $3n$ 角形の頂点を時計回りに $A_1,...,A_n,B_1,...,B_n,C_1,...,C_n$ とする．以下，問題文の条件を満たす写像 $f$ を**良い写像**と呼ぶ．良い写像は単射である．ある $1\leq i \leq n$ が存在して $\\{f(A_i),f(B_i),f(C_i)\\}=\\{A_n,B_n,C_n\\}$ が成り立つので，$i$ が $n$ と等しいかによって場合分けをする．

- $i=n$ のとき\
 $( f(A_n),f(B_n),f(C_n) )$ は $(B_n,C_n,A_n),(C_n,A_n,B_n)$ の $2$ 通りである．残り $3(n-1)$ 個の頂点を考えて，良い写像は $2a_{n-1}$ 個ある．

- $1\leq i \leq n-1$ のとき\
$f^2=f\circ f$ とする．\
　$(f^2(A_i),f^2(B_i),f^2(C_i))=(A_i,B_i,C_i),(A_i,C_i,B_i),(C_i,B_i,A_i),(B_i,A_i,C_i)$ ならば残り $3(n-2)$ 個の頂点を考えればよいのでこのような良い写像は $24(n-1)a_{n-2}$ 個ある．\
　そうでなければ，この写像 $f$ から，正 $3(n-1)$ 角形に対する良い写像 $f^\prime$ を次のように構成することで，正 $3(n-1)$ 角形に対する良い写像との一対一対応が得られる．
$$(f^\prime(A_k),f^\prime(B_k),f^\prime(C_k))=
\begin{cases}
(f(A_k),f(B_k),f(C_k))&(k\neq i)\\\\
(f^2(A_k),f^2(B_k),f^2(C_k))&(k=i)
\end{cases}$$
したがってこのような良い写像は $6(n-1)a_{n-1}$ 個ある．

以上より次の漸化式を得る．
$$a_n=2a_{n-1}+24(n-1)a_{n-2}+6(n-1)a_{n-1}$$
これを変形して次の式を得る．
$$a_n-6na_{n-1}=-4(a_{n-1}-6(n-1)a_{n-2})$$
これと $a_1=2,a_2=40$ より，数列 $\lbrace a_{n+1}-6(n+1)a_{n}\rbrace$ は初項 $16$，公比 $-4$ の等比数列である．
よって $a_{n+1}-6(n+1)a_{n}=(-4)^{n+1}$ なので次の計算が可能である．
$$\begin{aligned}
a_{100000}-\sum_{n=1}^{99999}(6n+5)a_n&=a_{100000}-\sum_{n=1}^{99999}(a_{n+1}-a_n-(-4)^{n+1})\\\\
&=a_1+\sum_{n=1}^{99999}(-4)^{n+1}\\\\
&=2+\frac{1}{5}(16+4^{100001})\\\\
&\equiv 2+\frac{1}{5}(16+\frac{1}{4})\pmod{100003}\\\\
&\equiv \frac{21}{4}\pmod{100003}\\\\
&\equiv \mathbf{25006}\pmod{100003}
\end{aligned}$$
公式解説
https://onlinemathcontest.com/contests/omc215/editorial/10031
$\\{1,2,\cdots,n\\}$ の置換 $\sigma$ に対してその固定点の個数を $F(\sigma)$ とすると
$$a_n=\sum_{\sigma}2^{F(\sigma)}6^{n-F(\sigma)}$$
が成り立つ（$n$個の正三角形がどのように入れ替わるかを指定したあと，それぞれの頂点がどのように入れ替わるかを指定することを考えればわかる）．$|F(\sigma)|=0$ となる置換の総数（モンモール数）を $M_n$ とすると，$|F(\sigma)|=k$ となる置換の総数は $\binom{n}{k}M_{n-k}$ なので
$$a_n=\sum_{k=0}^n\binom{n}{k}M_{n-k}2^k6^{n-k}$$
となる．よって$a_n$の指数型母関数は
$$\sum_{n=0}^\infty\dfrac{a_n}{n!}x^n=\biggl(\sum_{i=0}^\infty\dfrac{2^i}{i!}x^i\biggr)\biggl(\sum_{j=0}^\infty\dfrac{M_j6^j}{j!}x^j\biggr)=e^{2x}\cdot \dfrac{e^{-6x}}{1-6x} = \dfrac{e^{-4x}}{1-6x}$$
である．両辺に $1-6x$ を掛けると
$$\sum_{n=0}^\infty\dfrac{a_{n+1}-(6n+6)a_n}{(n+1)!}x^{n+1}=e^{-4x}$$
となるため $a_{n+1}-(6n+6)a_n$ が等比数列であることがわかる．あとは公式解説と同様である．
母関数を使う方法
https://onlinemathcontest.com/contests/omc215/editorial/10031/445
　正 $3n$ 角形があり，その頂点全体からなる集合を $S_n$ とします．次の条件をみたす写像 $f\colon S_n\to S_n$ の個数を $a_n$ とします：

- 任意の $S_n$ の要素 $a$ について $f(a)\neq a$．
- 任意の $S_n$ の相異なる要素 $a,b$ について $f(a)\neq f(b)$．
- $S_n$ の相異なる要素 $a,b,c$ が正三角形の頂点をなすならば $f(a),f(b),f(c)$ は正三角形の頂点をなす．

このとき，次の値を素数 $100003$ で割った余りを求めてください：
$$a_{100000}-\sum_{n=1}^{99999}(6n+5)a_n$$