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

<ul>
	<li>For example, <code>&quot;2582&quot;</code> is good because the digits (<code>2</code> and <code>8</code>) at even positions are even and the digits (<code>5</code> and <code>2</code>) at odd positions are prime. However, <code>&quot;3245&quot;</code> is <strong>not</strong> good because <code>3</code> is at an even index but is not even.</li>
</ul>

<p>Given an integer <code>n</code>, return <em>the <strong>total</strong> number of good digit strings of length </em><code>n</code>. Since the answer may be large, <strong>return it modulo </strong><code>10<sup>9</sup> + 7</code>.</p>

<p>A <strong>digit string</strong> is a string consisting of digits <code>0</code> through <code>9</code> that may contain leading zeros.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 5
<strong>Explanation:</strong> The good numbers of length 1 are &quot;0&quot;, &quot;2&quot;, &quot;4&quot;, &quot;6&quot;, &quot;8&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 4
<strong>Output:</strong> 400
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 50
<strong>Output:</strong> 564908303
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>15</sup></code></li>
</ul>

class Solution:
    MOD = 1000000007  # Define the modulo value as a constant
    
    def countGoodNumbers(self, n: int) -> int:
        # Calculate the number of positions for even and odd indices
        even_positions = n // 2 + n % 2  # Number of even index positions
        odd_positions = n // 2           # Number of odd index positions
        
        # Compute the total number of good strings
        # 5^even_positions for even indices and 4^odd_positions for odd indices
        even_count = self.binaryExp(5, even_positions)
        odd_count = self.binaryExp(4, odd_positions)
        
        return (even_count * odd_count) % self.MOD

    def binaryExp(self, base: int, exponent: int) -> int:
        # Binary exponentiation to compute (base^exponent) % MOD efficiently
        result = 1
        base %= self.MOD
        
        while exponent > 0:
            if exponent % 2 == 1:  # If exponent is odd, multiply base with result
                result = (result * base) % self.MOD
            base = (base * base) % self.MOD  # Square the base
            exponent //= 2  # Divide the exponent by 2
        
        return result
25