> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/recursion-and-backtracking/1922.-count-good-numbers.md).

# 1922. Count Good Numbers

## Problem Statement

<br>

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.

&#x20;

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

&#x20;

**Constraints:**

* `1 <= n <= 1015`

## Intuition

```
Approach:

We just have to find pow(n,x) in recursion

So we employ this trick

2^5 = 2^(2*2+1) = (2^2)^2 * 2 here, half is 2^2 now and since 5 is odd extra multiply
Go for 2^2 now 
```

### Links

<https://leetcode.com/problems/count-good-numbers/description/>

### Video Links

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    long mod=1e9+7;
    int countGoodNumbers(long n) {
        long even=(n+1)/2;
        long odd=n/2;

        return (int)(pow(5,even)*pow(4,odd)%mod);
    }
    long pow(long x,long n){
        if(n==0){
            return 1;
        }
        long half=pow(x,n/2);
        if(n%2==0){
            return (half*half)%mod;
        }
        return (half*half*x)%mod;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###