# 1922. Count Good Numbers
## 想法
每個奇數下標有4種可能，偶數下標有5種可能，每個下標互不影響，所以可以使用乘法原理
1 -> 1個偶數
2 -> 1奇1偶
3 -> 1奇2偶
...
n -> floor(n/2)奇ceil(n/2)偶, n is odd
n -> n/2奇n/2偶, n is even
## 演算法

1. 當n是奇數時，回傳4^floor(n/2)*5^ceil(n/2)
2. 回傳4^(n/2)*5^(n/2)

## 程式碼

#define mod 1000000007
class Solution {
public:
    int exp(int a, int b) {
        if (b == 0) return 1;
        if (b % 2) return exp(a, b - 1) * a % mod;
        int tmp = exp(a, b / 2);
        return (long long) tmp * tmp % mod;
    }
    int countGoodNumbers(long long n) {
        if (n % 2) return exp(4, n / 2) * exp(5, n / 2 + 1) % mod;
        return exp(4, n / 2) * exp(5, n / 2) % mod;
    }
};