405368: GYM101917 A Giga-Kilo-Gigabyte

As you probably already know one byte is 8 bits, 1024 bytes is 1 kilobyte, 1024 kilobytes are 1 megabyte, etc. The most common known prefixes to display units are the following:

$$$ 1000 units = 1 kilounit \\ 1000 kilounits = 1 megaunit \\ 1000 megaunits = 1 gigaunit \\ 1000 gigaunits = 1 teraunit \\ 1000 teraunits = 1 petaunit \\ 1000 petaunits = 1 exaunit \\ 1000 exaunits = 1 zettaunit \\ 1000 zettaunits = 1 yottaunit \\ $$$

Due to the fact that $$$2^{10}=1024$$$ is the closest number to 1000, we say that 1024 bytes are 1 kilobyte, for this problem we will ignore this rule of thumb and assume that 1000 bytes are 1 kilobyte. In the country of Diegolandia it is widely known that 1 zettabyte is $$$10^{21}$$$ bytes, however Diego knows that it's possible to prepend different prefixes and to stack them together to represent a higher amount, for example 1 gigabyte can be 1 kilo-kilobyte (1000 kilobytes). In the case of the zettabyte, Diego knows it can be represented as 1 giga-kilo-gigabyte ($$$10{^9}*10{^3}*10{^9}=10^{21}$$$), it can also be represented a 1 kilo-giga-gigabyte, or 1 exa-kilobyte, or 1 kilo-exabyte, etc. In this problem we only care about how many different ways Diego can prepend the different prefixes (all the way from kilo to yotta), since this number might be huge print it modulo $$$10{^9}+7$$$.

An integer T the number of test cases ($$$1<=T<=10{^5}$$$). Followed by T lines, each with 1 number N ($$$3<=N<10{^6}$$$), which means that Diego wants to know in how many ways he can prepend the different known prefixes to display units to represent the number $$$10^{N}$$$. It is guaranteed that N will be divisible by 3.

For each test case print a single line with a single integer representing the amount of ways Diego can prepend the known prefixes to display units to represent the number $$$10^{N}$$$, remember to print this number modulo $$$10{^9}+7$$$

5
3
6
9
12
24

1
2
4
8
128