Modular Exponentiation when only mod of a value is known

Question

I am trying to calculate $A^A$ % mod, where mod is $10^9 + 7$. I can calculate ($A$ % mod) for any value of mod but don't have direct access to A. How would I solve this?

Answer 1

Let $p=10^9+7$ and $a=A \bmod p$. This answer also assumes $\gcd(A,p)=1$.

Since $p\in\mathbb{P}$, $\phi(p)=p-1$ and therefore $a^{p-1}=1 \bmod p$.

Now let $b=A\bmod(p-1)$

Therefore $A^A\bmod p=a^b\bmod p$.

There are more efficient algorithms than above for modular exponentiation such as those discussed at the following link.

Wikipedia Article on Modular Exponentiation