A. The Giraffe and the Beautiful number
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For a positive integer $$$n$$$, define $$$f(n)$$$ to be the number of non-empty substrings of $$$n$$$ that are divisible by $$$3$$$. For example, the string $$$2573$$$ has $$$10$$$ non-empty substrings, three of which represent numbers that are divisible by $$$3$$$, namely $$$3$$$, $$$57$$$, and $$$573$$$. So $$$f(2573) = 3$$$.

The Giraffe thinks that if $$$f(n)$$$ is divisible by $$$3$$$, then we say that $$$n$$$ is a beautiful number.

Define $$$F(d)$$$ to be the number of $$$d$$$ digit numbers that are beautiful.

Find $$$F(d)$$$. Give your answer modulo $$$1\,000\,000\,007$$$.

Input

The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

Each test case consists of a single integer $$$d$$$ ($$$1 \le d \le 10^5$$$).

The sum of $$$d$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

Print the answer.

Example
Input
2
2
6
Output
30
290898