Baseline Recursion · Get Strong Hold O(log n) with fast exponentiation (the source uses O(n)) · O(n) recursion stack in the source form
A motor registry issues plate strings where every even position must carry an even digit and every odd position must carry one of the four single-digit primes. With five even digits and four primes available, each slot's freedom multiplies, and the registry needs the count of valid plates of any requested length modulo 10^9 + 7. The count grows by a factor of 5 per even slot and 4 per odd slot.
Input: A single integer n, the plate length.
Output: The number of valid digit strings of length n, modulo 10^9 + 7.
1 <= n <= 10^15Input: {"n":1}
Output: 5
One slot, which is even-indexed: any of the five even digits.
Input: {"n":4}
Output: 400
Two even slots and two prime slots: 5 * 4 * 5 * 4 = 400.