<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:

    def countGoodNumbers(self, n: int) -> int:
        mod = 1000000007
        even = (n+1)//2
        odd = n//2
        '''
            let n = 5

            _ _ _ _ _
            0 1 2 3 4

            even indices count = (n+1)/2
            odd indices count = n/2

            possible even numbers = [0, 2, 4, 6, 8] = 5 possibilities
            possible prime numbers = [2, 3, 5, 7] = 4 possibilities


            total possible permutations = 5^even * 4^odd
        '''
        # optimize this using power of x^n
        return (self.pow(5, even)%mod * self.pow(4, odd)%mod)%mod
    
    def pow(self, x, n):
        mod = 1000000007
        if n == 0:
            return 1
        elif n%2 == 0:
            return self.pow((x*x)%mod, n/2)
        else:
            return (self.pow((x*x)%mod, n//2)*x)
32