/* Programmer: Wes Weirather, Feb 2018, TA for Spring 2018 CS:3330, U of Iowa
import java.math.BigInteger;

class modPowerReference
{
    /** 
     * This should be similar to your moduloPower function in hw1.
     * You may use either your own fuction or this one in hw2.
     */
    public static BigInteger moduloPower(BigInteger a, BigInteger r, BigInteger p)
    {
        if (a.equals(BigInteger.ZERO))
        {
            return BigInteger.ZERO;
        }
        else if (r.equals(BigInteger.ZERO))
        {
            return BigInteger.ONE;
        }
        else if (r.equals(BigInteger.ONE))
        {
            return a.mod(p);
        }
        BigInteger[] halfr_rem = r.divideAndRemainder(BigInteger.valueOf(2));
        BigInteger s = moduloPower(a, halfr_rem[0], p).pow(2).mod(p);
        if (halfr_rem[1].equals(BigInteger.ONE))
        {
            s = s.multiply(a).mod(p);
        }
        return s;
    }

    /** This is the naive implementation. It is extremely inefficient for large inputs. */
    public static BigInteger slowModuloPower(BigInteger a, BigInteger r, BigInteger p)
    {
        BigInteger product = BigInteger.ONE;
        for (BigInteger i = BigInteger.ZERO; i.compareTo(r) < 0; i=i.add(BigInteger.ONE))
        {
            product = product.multiply(a).mod(p);
        }
        return product;
    }
}