OMC215(H)

点数: 400

Writer: natu_math

　正 $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$$