DAY 12 - Count Good Numbers

Hello to anyone reading this. I am still relatively new to coding and this platform as well, so please feel free to drop any corrections/advice for me.
I am trying to do the 100 Day-Challenge of consistent coding and this is Day-12.The goal is simple. I will solve one or more than one leetcode/gfg problem a day and post what I learnt. I am confident that this will help me improve my concepts and help me be more consistent in my practice. Looking forward to a positive interaction with all of you.

DAY - 12 Problem 1: Count Good Numbers

A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7).

For example, "2582" is good because the digits (2 and 8) at even positions are even and the digits (5 and 2) at odd positions are prime. However, "3245" is not good because 3 is at an even index but is not even.
Given an integer n, return the total number of good digit strings of length n. Since the answer may be large, return it modulo 109 + 7.

A digit string is a string consisting of digits 0 through 9 that may contain leading zeros.

Example 1:

Input: n = 1
Output: 5
Explanation: The good numbers of length 1 are "0", "2", "4", "6", "8".

Example 2:

Input: n = 4
Output: 400

Intuition and Approach:

Let's observe the problem closely. If we have a string of length 1. It means it has only 0 index.
Which means only even digits can come at this place. Hence the only possible options are 0,2,4,6 or 8.

1. Let's take this same approach for 2 digit length. Now another digit length is added. Hence our options are to put a prime number in it to make it good.
2. Our only options are the numbers 2,3,5 or 7. Hence a total of 4 options for prime and 5 options for even.
3. For every length, this remains constant that at every index we will either have 5 options or 4 options depending on the index position.
4. Looking closely odd length have 5^n/2 and even length 4^(n/2 + n%2) multiplied. Hence this will be our approach.
5. We will use a simple recursion program to find the power of the numbers and use math to find the final result.

Code:

long long power(long long x, long long n){
        if(n == 0){
            return 1;
        }
        long long ans = power(x, n/2);
        ans *= ans;
        ans %= 1000000007;
        if(n%2==1){
            ans *= x;
            ans %= 1000000007;
        }
        return ans;
    }
    int countGoodNumbers(long long n) {
        long long odd, even;
        odd = n/2;
        even = n/2 + n%2;
        return (power(5,even) * power(4,odd) % 1000000007);
        }

Complexity Analysis:

Time Complexity: O(logN)
Space Complexity: Recurion Stack