A digit is even if it's 0, 2, 4, 6, or 8. A digit is prime if it's 2, 3, 5, or 7. A number is good if digits at even indices (0, 2, 4, ...) are even digits, and digits at odd indices (1, 3, 5, ...) are prime digits.
Given , count how many -digit good numbers exist. Return the answer modulo .
For , you have 5 choices (0, 2, 4, 6, 8). For , the first digit has 5 choices, the second has 4 (2, 3, 5, 7). Total: .