Jackson House

문제

Jackson, after witnessing the advancements in the world of technology, decided to sell his small cozy house and enroll in the programming-and-algorithm micromaster. He came across an interesting algorithm that he needed to analyze and solve the problem related to it, in order to pass the exam at this stage of the course. The pseudocode of this algorithm is as follows:

input: a permutation &pi; = <&pi;_1, &pi;_2, \dots , &pi;_n> of numbers $\{1,2,\dots ,n\}\backslash \{1,\; 2,\; \backslash dots\; ,\; n\backslash \}$
while &pi; is changing during this iteration:
    for $i:=ni\; :=\; n$ downto $22$:
        if &pi;_i < &pi;_{\lfloor i/2 \rfloor}:
            swap(&pi;_i, &pi;_{\lfloor i/2 \rfloor})

He wants to know for how many permutations π of length $nn$ from the possible $n!n!$ ones, the final permutation will be sorted after running this algorithm.

입력

The first line contains an integer $tt$ ($1\le t\le 1001\; \backslash le\; t\; \backslash le\; 100$), the number of test cases.

Each of the next $tt$ lines contains an integer $n_{i}n\_i$ ($2\le n_i\le {10}^{9}2\; \backslash le\; n\_i\; \backslash le\; 10^9$), representing the length of the permutation for the $ii$^th test case.

출력

Output $tt$ lines. On the $ii$^th line, print the number of permutations of length $n_{i}n\_i$ which will be sorted after running the provided algorithm on it. Since the output could be very large, output the result modulo ${10}^9+710^9\; +\; 7$.