　カタツムリ君が $n$ 回目に辺を伝って移動した時に $X$ からの距離が $1,2,3,4$ の頂点にいる場合の数をそれぞれ，$a_n, b_n, c_n, d_n$ とすると，求める場合の数は $d_{9999}$ である．また，以下の漸化式が成り立つ．
$$
a_{n+1}=b_{n}, \quad
b_{n+1}=2a_{n}+b_{n}+c_{n}, \quad
c_{n+1}=b_{n}+c_{n}+2d_{n}, \quad
d_{n+1}=c_{n}
$$
ここで，$s_n = a_n + d_n, t_n = a_n - d_n$ とすれば，$d_{9999} = \dfrac{s_{9999}- t_{9999}}{2}$ であるから，$s_{9999}$ と $t_{9999}$ を $5003$ で割った余りを求めればよい．以下では，合同式は全て $5003$ を法として考える．

- $s_{9999}$ を $5003$ で割った余り\
$$s_{1} = 3,\quad s_2 = 0,\quad s_{n} = b_{n-1} + c_{n-1} = 2(b_{n-2} + c_{n-2}) + 2(a_{n-2} + d_{n-2}) = 2s_{n-1} +2 s_{n-2}$$
である．ここで，奇素数 $p$ と整数 $a$ に対し $\bigg(\dfrac{a}{p}\bigg)$ をLegendre記号とすると，平方剰余の相互法則より
$$\bigg(\dfrac{3}{5003}\bigg) = \bigg(\dfrac{5003}{3}\bigg)(-1)^{\frac{5003-1}{2}\cdot\frac{3-1}{2}} = 1$$
であるので，$r^2 \equiv 3$ なる整数 $r$ が存在する．このとき，
$$s_n \equiv \frac{r}{2}\big((1+r)(1-r)^{n-1} - (1-r)(1+r)^{n-1}\big)$$
であることが確認できる．従って，
$$\begin{aligned}
s_{9999} 
&\equiv \frac{r}{2}\big((1+r)(1-r)^{9998} - (1-r)(1+r)^{9998}\big)\\\\
&\equiv \frac{r}{2}\bigg(\frac{1+r}{(1-r)^6} - \frac{1-r}{(1+r)^6}\bigg)\\\\
&= \frac{r\big((1+r)^7 - (1-r)^7\big)}{2(1-r^2)^6}\\\\
&= \frac{\sum\limits_{k=1}^{4}{}\_{7}\mathrm{C}\_{2k-1}r^{2k}}{(1-r^2)^6}\\\\
&\equiv \frac{\sum\limits_{k=1}^{4}{}\_{7}\mathrm{C}\_{2k-1}3^k}{(-2)^6}\\\\
&\equiv \frac{123}{8}
\end{aligned}$$
である．もしくは，$s_{9999}\equiv s_{-5}$ であるから，漸化式を逆順に辿ることでも同様の結果を得られる．

- $t_{9999}$ を $5003$ で割った余り\
$$t_n = b_{n-1} - c_{n-1} = (2a_{n-2} + b_{n-2} + c_{n-2}) - (b_{n-2} + c_{n-2} + 2d_{n-2}) = 2(a_{n-2} - d_{n-2})$$
である．また，$a_1-d_1=3$ であるから，
$$a_{9999}-d_{9999}=3\times 2^{4999}\equiv 3\times2^{-3}\equiv \frac38$$
である．

以上より，求める答えは $d_{9999}\equiv\dfrac12\biggl(\dfrac{123}{8}-\dfrac38\biggr) \equiv \dfrac{15}{2}\equiv \bf{2509}$ である．
公式解説
https://onlinemathcontest.com/contests/omc144/editorial/6725
　正十二面体の頂点の一つを $X$ とし，中心に関して $X$ と対称な頂点を $Y$ とします．\
　カタツムリ君は，$X$ からスタートして，辺で結ばれた頂点に移動することを $10^4$ 回繰り返します．ここで，直前にいた頂点に引き返すことも可能です．このとき，以下の条件をみたす移動方法の総数を，素数 $5003$ で割ったあまりを求めてください．
　　　
- 一度も $X$ に戻らず，かつ $10^4$ 回目の移動で初めて $Y$ に到達する．

　ただし，回転して一致するような移動方法も異なるものとして数えます．