Count Position-Constrained Digit Strings
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Count length-`n` digit strings whose zero-based even positions contain an even digit and whose odd positions contain one of the prime digits `{2,3,5,7}`. Leading zeros are allowed. Return the number of strings modulo `1000000007`.
```cpp
class Solution {
public:
int countGoodNumbers(long long n);
};
```
### Examples
**Example 1:**
```text
n = 2
Output: 20
Explanation: Five choices at position 0 combine with four choices at position 1.
```
**Example 2:**
```text
n = 3
Output: 100
Explanation: The independent position counts multiply to 5*4*5.
```
### Constraints
- `1 <= n <= 10^15`.
### Clarifying Questions
These are fixed-length strings, so a zero in the first position is valid. Prime digits include 2.
```hint Inspect the structure
How many positions have each parity when n is odd?
```
### Reasoning checkpoints
- Count each permitted assignment of digits once, including leading zero and the extra even position when the length is odd.
- Meet the stated length bound and modulus while keeping intermediate arithmetic in range.
### Optional extensions
What changes if each residue class of positions has its own digit set?
Overview: Count Position-Constrained Digit Strings. Count decimal digit strings of length n whose zero-based even positions contain an even digit and whose odd positions contain a prime digit from {2,3,5,7}. Leading zeros are permitted. Return the count modulo 1000000007.