Given an integer n, count the number of good digit strings of length n, where positions at even indices can be filled with 0, 2, 4, 6, 8 and positions at odd indices can be filled with prime digits 2, 3, 5, 7. Return the answer modulo 1e9+7.
n = length of digit string
count of good digit strings modulo 1e9+7
Example 1:
Input:
n = 1
Output:
5
Explanation:
One position (index 0) has 5 choices.
Example 2:
Input:
n = 4
Output:
400
Explanation:
5 choices at positions 0 and 2, 4 choices at positions 1 and 3 => 5*4*5*4 = 400.