int power(int base, int exp)
{
    if(exp == 0)
        return 1;
    if(exp % 2 == 0)
        return base * base * power(base, exp/2);
    return base * power(base, exp-1);
}