Complexity of computing $n^{n^2}$
By using the fast Fourier transform, multiplications on $k$-bit numbers can be done in time $\tilde{O}(k)$ (where the tilde signifies that we're ignoring polylogarithmic factors). By repeated squaring, we can compute $n^{n^2}$ with $O(\log n)$ multiplications, and each multiplication involves no number larger than $n^{n^2}$, which has roughly $n^2 \log_2 n$ bits. So the total amount of time required is $\tilde{O}(n^2(\log n)^2)=\tilde{O}(n^2)$.