def powmod(a, b, m):
    """ Returns the power a**b % m """ 
    # a^(2b) = (a^b)^2
    # a^(2b+1) = a * (a^b)^2
    if b==0:
        return 1
    return ((a if b%2==1 else 1) * powmod(a, b//2, m)**2) % m