记 $n^!$ 为 $n^{n-1^{n-2^{...^1}}}$，给定 $n$ 与模数 $p$，求 $n^!$ $mod$ $p$ 的值。（$1 \le n \le 10^6$, $1 \le p \le 10^{12}$）。

不难想到光速幂与扩展欧拉定理，这也就意味这我们要预处理出 $\varphi(p)$ 与 $\varphi(\varphi(p))$...，那么现在是否存在在 $O(\sqrt{p})$ 的复杂度内预处理的做法呢？