Start

2018-07-09 14:40 UTC

sharpinfo3

End

2018-07-09 16:40 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -156 days 13:36:33

Time elapsed

2:00:00

Time remaining

0:00:00

Problem D
I Hate The Number Nine

/problems/nine/file/statement/en/img-0001.jpg

How many positive $d$ digit numbers exist that do not contain a nine?

Input

The first line of the input consists of a single integer, $T$, the number of test cases.
Each of the following $T$ cases consists of a single integer $d$, the number of digits.

  • $1 \leq T \leq 20$

  • $1 \leq d \leq 10^{18}$

Output

For each test case, output the number of positive numbers with $d$ digits that do not contain a nine. Since this number can be very large, output it modulo $1\, 000\, 000\, 007$.

Sample Input 1 Sample Output 1
3
1
2
100
8
72
343393926