Since can be up to , you can't compute 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 time. Without modular exponentiation, you'd time out.