Linear Recurrence for very large n
0 <= a, b, n <=  10^100
       1 <= M <= 100000
F(0)=1

// Requires n >= 0 and M > 0.
int modularPower(int a, int n, int M) {
    if (n == 0)
        return 1;
    int result = modularPower(a, n / 2, M);
    result = (result * result) % M;
    if (n % 2 != 0)
        result = (result * a) % M;
    return result;
}