Count Good Numbers

Problem Statement

A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7). Given an integer n, return the total number of good digit strings of length n. Since the answer may be large, return it modulo 10^9 + 7.

Example: n = 4 → Output: 400 (e.g., "2582" is good: even indices [2,8] are even, odd indices [5,2] are prime)
n = 1 → Output: 5 (only even digits 0,2,4,6,8 are valid)

Approach 1: Modular Exponentiation

Explanation: For even indices, there are 5 choices (0,2,4,6,8). For odd indices, there are 4 choices (2,3,5,7). Compute the number of good strings using fast exponentiation for 5^(even indices) * 4^(odd indices) modulo 10^9 + 7.

Time Complexity: O(log n)

Space Complexity: O(1)

mod = 10^9 + 7
function findPow(a, b):
    if b == 0:
        return 1
    half = findPow(a, b/2) % mod
    result = (half * half) % mod
    if b % 2 == 1:
        result = (result * a) % mod
    return result

evens = (n+1)/2
odds = n/2
return (findPow(5, evens) * findPow(4, odds)) % mod