// Arup Guha
// 12/4/2024
// Code with overflow error for CIS 3362 Final Exam

#include <stdio.h>

int func(int a, int b, int c);

// Test it.
int main() {
    printf("%d\n", func(302127, 53, 1234567));
    return 0;
}

// Thie calculates a raised to the power b modulo c.
int func(int a, int b, int c) {

    // Base case.
    if (b == 0) return 1;

    // Time savings here.
    if (b%2 == 0) {
        int t = func(a, b/2, c);
        return (t*t)%c;
    }

    // Regular exponentiation break down.
    return (a*func(a,b-1,c))%c;
}