Description

Jackson 在见证了科技世界的发展后，决定卖掉他舒适的小房子，并报名参加编程与算法微硕士项目。他遇到了一个有趣的算法，为了通过该课程此阶段的考试，他需要分析并解决与之相关的问题。该算法的伪代码如下：

$$\begin{array}{l} \textbf{输入：} \text{ 一个数字 } \{1, 2, \ldots, n\} \text{ 的排列 } \pi = \langle \pi_1, \pi_2, \ldots, \pi_n \rangle \\ \textbf{while } \pi \text{ 在本轮迭代中发生变化：} \\ \quad \textbf{for } i := n \textbf{ downto } 2: \\ \quad\quad \textbf{if } \pi_i < \pi_{\lfloor i/2 \rfloor}: \\ \quad\quad\quad \text{交换}(\pi_i, \pi_{\lfloor i/2 \rfloor}) \end{array}$$

他想知道，在长度为 $n$ 的所有 $n!$ 种可能排列 $\pi$ 中，有多少种排列在运行此算法后最终会变为有序排列。

Input Format

第一行包含一个整数 $t$ ($1 \leq t \leq 100$)，表示测试用例的数量。

接下来的 $t$ 行每行包含一个整数 $n_i$ ($2 \leq n_i \leq 10^9$)，表示第 $i$ 个测试用例中排列的长度。

Output Format

输出 $t$ 行。在第 $i$ 行中，输出长度为 $n_i$ 的排列中，在运行所提供的算法后会变为有序排列的数量。由于输出可能非常大，请将结果对 $10^9 + 7$ 取模后输出。

4
3
5
10
20

4
16
1728
23887872

Hint

翻译由 DeepSeek V3 完成