How to calculate modulus of remainder when a large number is divided by other.

Question

The problem is : I have to calculate the remainder for a very large number but if answer overflow, divides the result by $10^9+7$.

Let $a,b,c$ are numbers such that: $1\le a,b,c\le 10^{12}$. How to calculate $(a^b\,\%\,c) \mod 10^9+7$?

Answer 1

If $a$, $b$, $c$ are positive integers,$a^b \mod c$ can be calculated using repeated squaring mod $c$. That is, if $b = \sum_{j=0}^k b_j 2^j$ is the binary representation of $b$, first compute $x_j \equiv a^{2^j} \mod c$ by $x_0 = 1$, $x_{j+1} = x_j^2 \mod c$, then $a^b \equiv \prod_{b_j=1} x_j \mod c$.