Count Good Numbers - Implementation

Since $n$ can be up to $10^{15}$, you can't compute $5^{n/2}$ directly. Use modular exponentiation (the fast power function you learned earlier).

MOD = 10**9 + 7

def power(base, exp, mod):
    result = 1
    base = base % mod
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        exp = exp // 2
        base = (base * base) % mod
    return result

def countGoodNumbers(n):
    even_positions = (n + 1) // 2
    odd_positions = n // 2
    
    count_even = power(5, even_positions, MOD)
    count_odd = power(4, odd_positions, MOD)
    
    return (count_even * count_odd) % MOD

This runs in $O(\log n)$ time. Without modular exponentiation, you'd time out.