# PROBLEM LINK:

* Author:* Manish

*Neeraj*

**Tester:***Sumit*

**Editorialist:**# DIFFICULTY:

EASY.

# PREREQUISITES:

Math, Number theory.

# PROBLEM:

Ganesh Gaitonde is a student of Mathematics at PEOPLE’s University. These days he is busy with his girlfriend Kuku. On the other hand, Kuku don’t like mathematics that much. One day, Kuku decided to find all the strings of length N (comprising only of characters from ‘0’ to ‘9’) having an odd number of 0’s. For Example: 103,012,000 are all strings of length 3 having an Odd number of 0’s. She asked Gaitonde to find number of such strings of for a given length of string modulo 1000000009 (10^9 + 9). Gaitonde being busy in organizing college fest asks for your help. Help Gaitonde impressing his girlfriend.

# SOLUTIONS:

## Setter's Solution

```
#include <iostream>
```

#define m 1000000009

#define ll long long int

using namespace std;

ll modularExponentiation(ll x,ll n,ll M)

{

if(n==0)

return 1;

else if(n%2 == 0) //n is even

return modularExponentiation((x*x)%M,n/2,M);
else //n is odd
return (x*modularExponentiation((x*x)%M,(n-1)/2,M))%M;

}

int main()

{ ll n;

int t;

cin>>t;

while(t–)

{

cin>>n;

ll x=modularExponentiation(10,n,m);

ll y=modularExponentiation(8,n,m);

```
cout<<(((x-y+m)%m)*(modularExponentiation(2,m-2,m)))%m<<endl;
```

}

return 0;

}

## Tester's Solution

indent whole code by 4 spaces

## Editorialist's Solution

indent whole code by 4 spaces