　$p-1 = 2^6 \cdot 3^2 \cdot 5 \cdot 7$ である．また，該当範囲で $x$ が $p$ の倍数になるものは無視してよい．ここで，$\bmod~p$ での原始根の一つを $r$ とする．$p$ 以上 $p^3$ 未満の整数のうち $p$ を法として $r^k$ $(0\leq k \lt p-1)$ と等しいものは，$r^k$ を $p$ で割った余りを $a_k$ とすると $bp+a_k$ $(1\leq b \leq p^2-1)$ と表せることから，$p^2-1$ 個存在する．この集合を $S_k$ とする．$x \in S_k$ について $x^x$ の $p$ での剰余を考えると，フェルマーの小定理より，
$$
x^x = (bp+a_k)^{bp+a_k}
\equiv a_k^{bp+a_k} 
\equiv r^{k(b+a_k)}  \pmod{p}
$$
となり，上記の値が $\mathrm{mod} ~ p$ で $1$ となることから，原始根の性質から
$$
k(b+a_k) \equiv 0 \pmod{p-1}
$$
である．$1 \leq b \leq p^2-1$ より，$b+a_k$ を $p-1$ で割った余りは $0, 1, \ldots, p-2$ がちょうど $p+1$ 回ずつ登場する．したがって，$0$ 以上 $p-1$ 未満の整数の組 $(s,t)$ であって，$st$ が $p-1$ で割り切れるものの個数を $p+1$ 倍したものが答えとなる．以下ではこれを求める．\
　$s$ を固定したときに，$g=\gcd(s,p-1)$ とすると，$t$ は $\dfrac{p-1}{g}$ の倍数であるから，$t$ としてあり得るものは $g$ 個存在する．これを足し合わせることで，結局
$$
(p+1) \sum_{s=1}^{p-1} \gcd(s,p-1)
$$
を計算すればよい．$f(n)=\sum_{s=1}^{n} \gcd(s,n)$ とおく．

**補題．** $x,y$ を互いに素な正整数とすると，$f(xy)=f(x)f(y)$ が成り立つ．

<details><summary>**証明**<\/summary>
　$n$ の正の約数 $d$ を任意にとる．$\phi$ をオイラーのトーシェント関数とする．$\gcd(k,n)=d$ を満たす正整数 $k$ の個数は，$\gcd(k,n\/d)=1$ を満たす $k$ の個数，すなわち $\phi(\frac{n}{d})$ 個である．したがって，
$$
\begin{aligned}
f(n) &= \sum_{k=1}^n \gcd(k,n)\\\\
& = \sum_{d|n} d\phi \bigg(\frac{n}{d}\bigg)\\\\
& = n\sum_{d|n} \frac{\phi (d)}{d}
\end{aligned}
$$
となる．ここで，互いに素な二つの正整数 $x,y$ に対して
$$
\phi(xy)=\phi(x)\phi(y)
$$
であるから，
$$
\begin{aligned}
f(xy) &= xy\sum_{d|xy} \frac{\phi (d)}{d}\\\\
&= xy\sum_{d_1|x,d_2|y} \frac{\phi (d_1d_2)}{d_1d_2}\\\\
&= xy\bigg(\sum_{d_1|x} \frac{\phi (d_1)}{d_1}\bigg)\bigg(\sum_{d_2|y} \frac{\phi (d_2)}{d_2}\bigg)\\\\
&= f(x)f(y)
\end{aligned}
$$
が成立する．
<\/details>

補題により，以下のように計算できる．
$$
\begin{aligned}
f(p-1) &= f(2^6)f(3^2)f(5)f(7)\\\\
&=(1\cdot 32 + 2 \cdot 16 + 4\cdot 8 +  8\cdot 4 + 16 \cdot 2 + 32\cdot 1 + 64)(1\cdot 6 + 3 \cdot 2 + 9)(1\cdot 4 + 5)(1\cdot 6 + 7)\\\\
&= 628992
\end{aligned}
$$
よって，これを $p+1$ 倍した $628992 \cdot 20162 = \mathbf{12681736704}$ 個が答えである．
公式解説
https://onlinemathcontest.com/contests/omc239/editorial/10644
　$p=20161$ とします． $p$ 以上 $p^3$ 未満の整数 $x$ であって，$x^x-1$ が $p$ で割り切れるものはいくつありますか．ただし，$20161$ は素数です．