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.

&nbsp;
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


Example 3:

Input: n = 50
Output: 564908303


&nbsp;
Constraints:


	1 &lt;= n &lt;= 1015


class Solution:
    def countGoodNumbers(self, n: int) -> int:
        ans = 1
        rem = n % 2
        n -= rem
        ans = pow(20, n//2, 10**9 + 7)
        if rem == 1:
            ans *= 5
        return ans % (10**9 + 7)
class Solution {
    int mod=(int)1e9+7;
    public int countGoodNumbers(long n) {
        long first=(n%2==0?(n/2):(n/2)+1);//deciding n/2 or n/2+1 depending on n is even or odd
        long second=n/2;//second power would be n/2 only irrespective of even or odd
        long mul1=power(5,first)%mod;//5 power n/2
        long mul2=power(4,second)%mod;//4 power n/2
        long ans=1;
        ans=(ans*mul1)%mod;//computing total product
        ans=(second!=0)?(ans*mul2)%mod:ans;//computing total product
        return (int)(ans%mod);
    }
    public long power(long x,long y){// this method computes pow(x,y) in O(logn) using divide & conquer
        long temp;
        if(y==0) return 1;//base case (x power 0 = 1)
        temp=power(x,y/2);//computing power for pow(x,y/2) -> divide & conquer step
        if(y%2==0) return (temp*temp)%mod; //using that result of subproblem (2 power 2 = 2 power 1 * 2 power 1)
        else return (x*temp*temp)%mod;//using that result of subproblem (2 power 3 = 2 power 1 * 2 power 1 * 2)
		// if y is odd, x power y = x power y/2 * x power y/2 * x
		// if y is even, x power y = x power y/2 * x power y/2
    }
}
// Approach :-> This is question of combination
// if n as large no....
// 0 1 2 3 4 5 6 7 8 9 10 11 . . . . . n
// 5 * 4 * 5 * 4 * 5 * 4 * 5 * 4 * 5 * 4 * 5 * 4 . . . . . n/4 times of 4 and n/4 times of 5;
//so calculate 5*4 = 20 -------> 20 * 20 * 20 * . . . . .. n/2 times
//so calcultae pow(20,n/2)
// if n is even return pow(20,n/2)
// if n is odd return 5*pow(20,n/2) beacause if n is odd then one 5 is left out
// we can easily calculate pow(x,y) in log(y) times
// durign calculation take care about mod
class Solution {
public:
    int mod = 1000000007;
    long long solve(long long val,long long pow){ // calculatin pow in log(n) time
        if(pow==0) return 1;

        if(pow%2==0){
            return solve((val*val)%mod,pow/2)%mod;
        }
        else
            return (val*solve((val*val)%mod,pow/2))%mod;

    }
    int countGoodNumbers(long long n) {
        // even means 5 options
        // odd means 4 option

        long long pow = n/2; // calculate no of times 5*4 means 20 occurs

        long long ans = solve(20,pow); // calculate power(20,pow)

        if(n%2==0){ // if n is even then 5 and 4 occur same no of time n/2
            return ans;
        }
        return ((5*ans) % mod); // if n is odd then 5 occurs n/2+1 times means one extra times so return ans*5 and don't forgot to mod
    }
};
class Math1 {

    // https://en.wikipedia.org/wiki/Modular_exponentiation
    static modular_pow(base, exponent, modulus) {
        if (modulus === 1n)
            return 0n
        let result = 1n
        base = base % modulus
        while (exponent > 0n) {
            if (exponent % 2n == 1n)
                result = (result * base) % modulus
            exponent = exponent >> 1n
            base = (base * base) % modulus
        }
        return result
    }

}

var countGoodNumbers = function(n) {
    // NOTE: 0n, 1n, 2n, 3n, 4n, 5n are numbers in BigInt

    n = BigInt(n); // convert to BigInt, to avoid no rounding issues

    const odds = n / 2n,
        evens = n - odds,
        MOD = BigInt(Math.pow(10, 9) + 7)

    // from wikipedia
    return (Math1.modular_pow(4n, odds, MOD) * Math1.modular_pow(5n, evens, MOD)) % MOD;
};
Count Good Numbers