Akash's Girlfriend
Tag(s):

## Algorithms, Combinatorics, Mathematics, Medium

Problem
Editorial
Analytics

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

Input:

First line of input contains an integer t(t<=10000) which is the number of test cases, then, t lines follow each containing an integer N <= 10^18

Output:

For each test case print single integer, the number of strings of length N comprising only of characters from '0' to '9'. Having odd number of zeroes.

SAMPLE INPUT
2
1
2

SAMPLE OUTPUT
1
18

Explanation

Case 1: only possible case is '0'. Case 2: The following string of length 2 contains odd number of zeroes: 01,02...,09,10 --> 10 numbers 20,30,...,90 ---> 8 numbers total 18 numbers

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

February Love

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Data Structures > Advanced Data Structures
• Math > Combinatorics
Уведомления

?