18.md

COUNT GOOD NUMBERS

Practice public: int mod=1e9 +7; long long find(long long i,long long r) { if(r==0) return 1;

    long long ans=find(i,r/2);
    ans=(ans*ans)%mod;

    if(r%2==1)
        return (ans*i)%mod;
    return ans;    
}
int countGoodNumbers(long long n) {
    
    long long noOfOddPlaces=n/2;
    long long noOfEvenPlaces=n/2 +n%2;

    return (find(5,noOfEvenPlaces) *find(4,noOfOddPlaces))%mod;
}