public class Power
{
  public static void main(String args[]){
    System.out.println(power(3,7));
    System.out.println(power(7,9));
    System.out.println(power_linear(3,7));
    System.out.println(power_linear(7,9));
  }
  
  static int power(int x, int p){
    int tmp;
    
    // Terminating condition
    if(p == 0)
      return 1;
      
    tmp = power(x, p/2);
    if( p % 2 == 0 ){
      // p is even
      return tmp*tmp;
    }else{
      // p is odd
      return tmp*tmp*x;
    }
  }
  
  static int power_linear(int x, int p){
    int i, result;
    result = 1;
    
    for(i = 0, result = 1; i < p; i++, result *= x);
    
    return result;
  }
}