Formatted question description: https://leetcode.ca/all/1922.html

# 1922. Count Good Numbers

## Level

Medium

## Description

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

`10^9 + 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

**Example 3:**

**Input:** n = 50

**Output:** 564908303

**Constraints:**

`1 <= n <= 10^15`

## Solution

A good digit string has five possible digits at each even index and four possible digits at each odd index. For each pair of adjacent indices, there are 20 possible values. Let `n = 2 * m + k`

where `m`

is an integer and `k`

is either 0 or 1, and the number of good digits with length `n`

is `m^20*5^k`

.

```
class Solution {
static final int MODULO = 1000000007;
public int countGoodNumbers(long n) {
long halfN = n / 2;
int remainder = (int) (n % 2);
long count = myPow(5 * 4, halfN);
if (remainder == 1)
count *= 5;
count %= MODULO;
return (int) count;
}
public long myPow(long x, long n) {
long power = 1;
while (n > 0) {
if (n % 2 == 1)
power = power * x % MODULO;
x = x * x % MODULO;
n /= 2;
}
return power;
}
}
```