Math Fast power and modular arithmetic
99. Count Good Numbers
A string of digits is good when every digit at an even index is even, and every digit at an odd index is prime. Indexes count from 0 at the left, so the first digit sits at an even index.
The even digits are 0, 2, 4, 6 and 8. The prime digits are 2, 3, 5 and 7. So "4725" is good: 4 and 2
sit at indexes 0 and 2 and are even, and 7 and 5 sit at indexes 1 and 3 and are prime. "4729" is not
good, because 9 is not prime. A string may start with 0, so "0" and "03" are good.
Given an integer n, return how many good strings of length n there are. The count grows very fast,
so return it modulo 109 + 7, which means the remainder after dividing it by 1,000,000,007.
Example 1
Input: n = 4
400Explanation: Indexes 0 and 2 can each hold any of the 5 even digits, and indexes 1 and 3 any of the 4 prime digits.
So there are 5 × 4 × 5 × 4 = 400 good strings, from "0202" to "8787".
Example 2
Input: n = 1
5Explanation: The good strings of length 1 are "0", "2", "4", "6" and "8".
Example 3
Input: n = 1000000000000000
711414395Explanation: The count itself has hundreds of trillions of digits. 711414395 is its remainder after dividing by 1,000,000,007.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ n ≤ 1015
Clarifying questions
What you would ask an interviewer before writing any code.