316. Good Digit Strings
A lock company designs numeric codes made of exactly n decimal digits (leading zeros are allowed). A code is called good when every digit at an even position is an even digit (0, 2, 4, 6 or 8) and every digit at an odd position is a prime digit (2, 3, 5 or 7). Positions are counted from 0 at the left.
Return how many good codes of length n exist. The count can be astronomically large, so return it modulo 1,000,000,007. Because n can reach 10^15, you cannot multiply digit by digit; compute the needed powers by repeated squaring, with a recursive helper that halves the exponent.
Example 1
- Input:
- n = 4
- Output:
- 400
- Explanation:
Positions 0 and 2 each have 5 choices and positions 1 and 3 each have 4 choices, giving 5 x 4 x 5 x 4 = 400.
Example 2
- Input:
- n = 50
- Output:
- 564908303
- Explanation:
There are 25 even positions and 25 odd positions, so the count is 5^25 x 4^25 modulo 1,000,000,007, which is 564908303.
Constraints
1 ≤ n ≤ 1015
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log n)
- Space
- O(log n)