def pow__mod_c(a, k, c):
    """computes a^k (mod c), 
       we assume a,k>=1, c > 1 integers"""
    
    if (k == 0):
        return 1
    elif (k & 1):
        return ((a * pow__mod_c(a, k//2, c)**2) % c)
    else:
        return ((pow__mod_c(a, k//2, c)**2) % c)