Check this: Fermat's Little Theorem

According to Fermat's Little Theorem, for some prime $$$p$$$

$$$a ^ {p - 1} \equiv 1 \pmod p $$$

Now suppose we have to find $$$ a ^ {x} \pmod p $$$ We can write $$$x$$$ as $$$k * (p - 1) + r$$$ where $$$r$$$ is the remainder when we divide $$$x$$$ by $$$p - 1$$$ for some constant $$$k$$$

$$$ a ^ {x} = a ^ {k * (p - 1) + r} \pmod p $$$

$$$ a ^ {k * (p - 1) + r} = a ^ {{(p - 1)} * {k}} * a ^ {r} \pmod p$$$

$$$a ^ {{(p - 1)} * {k}} * a ^ {r} = 1 ^ {k} * a ^ {r} \pmod p $$$ Since $$$a ^ {p - 1} \equiv 1 \pmod p $$$

Hence

$$$ a ^ {x} \equiv a ^ {r} \pmod p $$$ where $$$r = x$$$ % $$$(p - 1)$$$

and how do you calculate it with 10^9 + 6?