import java.io.*;
import java.util.*;
import java.math.*;

public class FastExponentiation {

  public static void main(String [] args) {

    BigInteger a = new BigInteger(args[0]);
    int b = Integer.parseInt(args[1]);
    numMultiplications = 0;
    BigInteger result = new FastExponentiation().power(a,b);
    System.out.println("numMultiplications = " + numMultiplications);
    System.out.println(a + " ^ " + b + " = " + result);
  }


  public BigInteger power(BigInteger base, int exponent) {
    if (exponent == 1) return base;
    if (exponent == 0) return BigInteger.ONE;

    BigInteger intermediate = power( base, exponent/2);    
    BigInteger result = intermediate.multiply(intermediate);
    numMultiplications++;

    if ((exponent & 1) == 1) {
      numMultiplications++;
      return result.multiply(base);
    }
    return result;
  }

  public static int numMultiplications = 0;
    
}