H. Halting Zero Permutation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A permutation of size $$$m$$$ is a sequence of $$$m$$$ positive integers containing each number from $$$1$$$ to $$$m$$$ exactly once. For example, $$$[1,4,5,3,2]$$$ is a permutation of size $$$5$$$, while $$$[1,1,4,3,5]$$$ and $$$[1,6,2,3,4]$$$ are not.

For an even-length sequence $$$[A_1, A_2, \ldots, A_{2t}]$$$, we define its power-product value ($$$\Lambda(A)$$$) as the product of terms obtained by taking each consecutive pair $$$(A_{2i-1}, A_{2i})$$$, raising the first element to the power of the second, and multiplying all such results together. Formally,

$$$$$$ \Lambda(A) = \prod_{i=1}^{t} A_{2i-1}^{\,A_{2i}} = (A_1^{A_2}) \cdot (A_3^{A_4}) \cdot (A_5^{A_6}) \cdot \ldots \cdot (A_{2t-1}^{A_{2t}}). $$$$$$

For example, if $$$A = (3,2,5,6,4,1)$$$, then $$$\Lambda(A) = 3^2 \cdot 5^6 \cdot 4^1 = 562500$$$

Next, we define a halting zero value of a number as equal to how many trailing zeros an integer has. For a positive integer $$$x$$$, let the halting zero function $$$\mho_0(x)$$$ be the number of zeros at the end of its decimal representation. Formally:

$$$$$$ \mho_0(x) = \max \{ k \in \mathbb{Z}_{\geq 0} : 10^k \mid x \}. $$$$$$

For example, $$$\mho_0(12000) = 3, \mho_0(907) = 0$$$

Your task is to find $$$ \max_{P} \mho_0(\Lambda(P))$$$ when $$$P$$$ is a permutation of size $$$2N$$$. Because the answer may be extremely large, output the result modulo $$$10^9+7$$$.

Input

The first line contains a single integer $$$T$$$ — the number of test cases. $$$(1 \le T \le 1000)$$$

Each of the next $$$T$$$ lines contains a single integer $$$N$$$. $$$(1 \le N \le 10^{12})$$$

Output

For each test case, output a single integer — the maximum value of $$$\mho_0(\Lambda(P))$$$ modulo $$$10^9+7$$$.

Example
Input
4
2
3
5
13
Output
0
6
17
142
Note

For $$$N = 3$$$ : Let $$$P = (5,6,4,3,2,1)$$$, then $$$\mho_0(\Lambda(P)) = \mho_0(5^6 \cdot 4^3 \cdot 2^1) = \mho_0(2,000,000) = 6$$$, which is the maximum value.

For $$$N = 5$$$ : Let $$$P = (4,2,3,6,5,9,1,7,10,8)$$$, then $$$\mho_0(\Lambda(P)) = \mho_0(4^2 \cdot 3^6 \cdot 5^9 \cdot 1^7 \cdot 10^8)$$$ $$$= \mho_0(2,332,800,000,000,000,000,000) = 17$$$, which is the maximum value.