count-good-numbers

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

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

<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 not good because <code>3</code> is at an even index but is not even.</li>
</ul>

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

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

&nbsp;
Example 1:

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

Example 2:

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

Example 3:

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

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 1015</code></li>
</ul>