Jackson 在见证了科技世界的进步后，决定卖掉他那温馨的小房子，并报名参加了程序与算法微硕士课程。他遇到了一个有趣的算法，他需要分析并解决与之相关的问题，以便通过该阶段课程的考试。该算法的伪代码如下：

输入：一个由数字 $\{1, 2, \dots, n\}$ 组成的排列 $\pi = \langle \pi_1, \pi_2, \dots, \pi_n \rangle$ 当 $\pi$ 在此轮迭代中发生变化时：     对于 $i := n$ 递减到 $2$：         如果 $\pi_i < \pi_{\lfloor i/2 \rfloor}$：             $\text{swap}(\pi_i, \pi_{\lfloor i/2 \rfloor})$

他想知道，在所有 $n!$ 个可能的长度为 $n$ 的排列 $\pi$ 中，有多少个排列在运行该算法后，最终的排列会被排好序（升序）。

输入格式

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

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

输出格式

输出 $t$ 行。在第 $i$ 行中，输出长度为 $n_i$ 且在运行上述算法后能够被排好序的排列数量。由于输出可能非常大，请将结果对 $10^9 + 7$ 取模后输出。

样例

输入样例 1

4
3
5
10
20

输出样例 1

4
16
1728
23887872