Jjin Even Number

Interview

Time limit1sMemory limit1024 MB

Summary

Given N, count the N-digit Jjin Even Numbers (no leading zero, except 0 itself) modulo 10^9+7 for up to 100,000 queries.

Level: Easy2 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Recently, Chito defined a unique kind of number called Jjin Even Number. A Jjin Even Number is a non-negative integer with $N$ digits in which every digit belongs to $\{0, 2, 4, 6, 8\}$ . Apart from 0 itself, numbers that start with 0, such as $0246$ , are not considered. For example, $468$ and $660$ are Jjin Even Numbers, but $14$ and $567$ are not.

Minseong became curious about Jjin Even Numbers and wants to ask Chito $Q$ questions. Each question has the following form:

$N$ : the number of distinct Jjin Even Numbers among the non-negative integers with $N$ digits

Help Chito answer the $Q$ questions.

Input

The first line contains a positive integer $Q$ , the number of questions. $(1 \leq Q \leq 100\,000)$

Each of the next $Q$ lines contains a positive integer $N$ , the question to ask Chito. $(1 \leq N \leq 10^7)$

Output

Print $Q$ lines. On each line, print Chito's answer modulo $10^9+7$ .

Examples1

Example 1
Input
```
2
1
2
```
Expected output
```
5
20
```