1922. Count Good Numbers

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        """ tc O(lgN) sc O(lgN)
        """
        M = 10**9+7
        def mod_pow(val, cnt):
            res = 1
            while cnt:
                if cnt%2==1:
                    res = val* res 
                cnt = cnt//2 
                val = (val*val)%M
            return res
        even_cnt = n//2 
        odd_cnt = n - even_cnt
        return (mod_pow(4,even_cnt)%M * mod_pow(5,odd_cnt)%M)%M
#mod_pow(20,even_cnt)* (1 if n%2 == 0 else 5) %M