Calculating the last 100 digits of 9^9^9^9 with Python

tower_mod.py

def phi_2_5(m):
    """Computes the totient of a number m whose only prime factors are 2 or 5."""
    if m % 2 == 0:
        m //= 2
    if m % 5 == 0:
        m = (m * 4) // 5
    return m

def tower_mod(a, n, m):
    """Evaluates the power tower a^a^a^..^a, with height n, modulo m.
    It is assumed that the only prime factors of m are 2 or 5, 
    but a is *not* divisible by 2 or 5."""
    print(n, m)
    if n == 1:
        return pow(a, 1, m)
    else:
        e = tower_mod(a, n - 1, phi_2_5(m))
        return pow(a, e, m)

# Example: Calculate the last 100 digits of 9^9^9^9
print(tower_mod(9, 4, 10**100))

# Expected result:
# 3771540670946945552331518959254852001991324340257630363975097419408973491530163140828233401045865289