　$1$ 以上 $p-1$ 以下の $a,b$ に対し, $a^{p-8}\equiv{b}^{p-8} \pmod{p}$ のとき, Fermatの小定理より $a^{p-1}\equiv{b}^{p-1}\pmod{p}$ でもあるから, $\mathrm{gcd}(p-8,p-1)=\mathrm{gcd}(7,p-1)=1$ に注意して $a\equiv{b}\pmod{p}$ であることがわかる. これは、$1^{p-8},2^{p-8},\cdots,(p-1)^{p-8}$ を $p$ で割った余りはすべて相異なることを意味するので, $a_1+a_2+\cdots+a_p$ が $p$ の倍数となる $1$ 以上 $p-1$ 以下の整数の組 $(a_1,a_2,\cdots,a_p)$ の総数を求めればよい.\
　一般に $a_1+a_2+\cdots+a_n$ が $p$ の倍数となる $1$ 以上 $p-1$ 以下の整数の組 $(a_1,a_2,\cdots,a_n)$ の総数を $x_n$ とおくと, $a_1+\cdots+a_{n-1}$ が $p$ の倍数でないとき適する $a_n$ が一意に存在するから, 漸化式 $x_{n+1}=(p-1)^n-x_{n}$ を得る. $x_1=0$ を加味してこれを解けば,  以下のようになることが容易にわかる.
$$x_n=\frac{(p-1)^n+(-1)^n\times(p-1)}{p}$$
　いま $\varphi$ をEulerのtotient関数とすれば $\varphi(625)=500$ から
$$(p-1)^p\equiv6^7\equiv279936\equiv-64\pmod{625}$$
であり, $(p-1)^p$ は $16$ の倍数であることを加味して $(p-1)^p\equiv-64\pmod{10000}$ となる. よって
$$x_p=\frac{(p-1)^p+(-1)^p\times(p-1)}{p}\equiv\frac{-64-6}{7}\equiv -10\equiv\textbf{9990} \pmod{10000}$$
公式解説
https://onlinemathcontest.com/contests/omc067/editorial/2290
　$p=10^9+7$ は素数です. $a_1^{10^9-1}+a_2^{10^9-1}+\cdots+a_p^{10^9-1}$ が $p$ の倍数となるような, $1$ 以上 $p-1$ 以下の整数の順序付いた組 $(a_1,a_2,\ldots,a_p)$ の総数を $N$ とおきます. $N$ を $10000$ で割った余りを求めてください.