Leetcode 1922. Count Good Numbers

Count the number of length-n digit strings where digits at even indices must be even (5 choices) and digits at odd indices must be prime (4 choices); the total is 5^{ceil(n/2)} * 4^{floor(n/2)} modulo 10^9+7. Because n can be up to 10^15, compute powers with fast modular exponentiation.