Count Good Numbers

Medium · Math & Number Theory · about 15 minutes

Asked at Amazon, Google, Microsoft, Bloomberg, Meta.

A string of decimal digits is good when each digit in an even position (counting from 0) is even (0, 2, 4, 6 or 8) and each digit in an odd position is a prime digit (2, 3, 5 or 7). Leading zeros are fine. Count the good strings of length n modulo 10⁹ + 7. (In general n can reach 10¹⁵; in these tests it fits in 32 bits.)