from lib_prime import prime_factors


def phi(n):
    # Calculate phi using Euler's totient function
    c = n
    fs = set(prime_factors(n))
    for f in fs:
        # same as c *= (1 - 1/f)
        c *= (f - 1)
        c //= f
    return c


def tetmod(a, k, m):
    # https://stackoverflow.com/questions/30713648/how-to-compute-ab-mod-m
    assert k > 0
    if k == 1:
        return a
    if m == 1:
        if a % 2 == 0:
            return 0
        else:
            return 1
    phi_m = phi(m)
    return pow(a, phi_m + tetmod(a, k - 1, phi_m), m)


def euler_188():
    assert phi(100) == 40
    assert tetmod(14, 2016, 100) == 36
    return tetmod(1777, 1855, 10**8)


if __name__ == "__main__":
    solution = euler_188()
    print("e188.py: " + str(solution))
    assert solution == 95962097