Your task is to create a new implementation of `modpow` so that it computes `(x^y)%n` for large `y`. The problem with the current implementation is that the output of `Math.pow` is so large on our inputs that it won't fit in a 64-bit float.

You're also going to need to be efficient, because we'll be testing some pretty big numbers.

Difficulty: introductory

Starter code:

def power_mod(b, e, m):
	

Solutions:
def power_mod(b, e, m):
  res, b = 1, b % m
  while e > 0:
    if e & 1: res = res * b % m
    e >>= 1
    b = b * b % m
  return res

def power_mod(base, exponent, modulus):
    if base is 0: return 0
    if exponent is 0: return 0
    base = base % modulus
    result = 1
    while (exponent > 0):
        if (exponent % 2 == 1):
           result = (result * base) % modulus
        exponent = exponent >> 1
        base = (base * base) % modulus
    return result

def power_mod(x, a, n):
    ret = 1
    x = x % n
    while a:
        (a, r) = divmod(a, 2)
        if r:
            ret = ret * x % n
        x = x ** 2 % n
    return ret


def rests(n, b):
    rests = []
    while n:
        n, r = divmod(n, b)
        rests.append(r)
    return rests

# k-ary LR method (~800 ms)
def power_mod(x, y, n, k=5):
    base, table, res = 2 << (k-1), [1], 1
    for i in range(1, base):
        table.append(x*table[i-1] % n)
    for rest in reversed(rests(y, base)):
        for _ in range(k): res = res*res % n
        if rest: res = res*table[rest] % n
    return res

def power_mod(a, b, n):
    res = 1
    while b:
        if b % 2:
            res = res * a % n
        a = a * a % n
        b = b // 2
    return res

from math import floor
def power_mod(base, exponent, modulus):
    if (base < 0) or (exponent < 0) or (modulus < 1):
       return -1
    result = 1
    while exponent > 0:
        if (exponent % 2) == 1:
            result = (result * base) % modulus
        base = (base * base) % modulus
        exponent = floor(exponent / 2)
    return result

def power_mod(x, y, n):
    x = x%n
    b = bin(y)[2:]
    l = len(b)
    res = [0]*l
    for i in range(l):
        res[-i-1] = x
        x *= x
        x = x%n
    prod = 1
    for i in range(l):
        if b[-i-1] == '1':
            prod *= res[-i-1]
            prod = prod%n
    return prod

def power_mod(b, e, m):
    r, b = 1, b % m
    while e > 0:
        if e % 2 == 1: r = (r * b) % m
        e, b = e >> 1, (b * b) % m
    return r