# Programmer: Wes Weirather, Feb 2018, TA for Spring 2018 CS:3330, U of Iowa
import random

"""
This should be similar to your moduloPower function in hw1.
You may use either your own fuction or this one in hw2.
"""
def moduloPower(a, r, p):
    if a == 0:
        return 0
    elif r == 0:
        return 1
    elif r == 1:
        return a % p
    s = moduloPower(a, r//2, p)**2 % p
    if r % 2 == 1:
        s = a*s % p
    return s

"""This is the naive implementation. It is extremely inefficient for large inputs."""
def slowModuloPower(a, r, p):
    return a**r % p