题目描述

老师定义一个函数 $f(p), p$ 为排列，令 $g_{i}$ 等于 $g c d\left(p_{1}, p_{2}, \ldots, p_{i}\right)$ ，那么 $f(p)$ 等于 $g_{i}$ 不同的数的个数。 令 $f_{\text {max }}(n)$ 等于所有 1 到 $n$ 的排列中最大的 $f(p)$ 。 给出老师要你求出对于所有 1 到 $n$ 的排列 $p, f(p)=f_{\max }(n)$ 的个数，答案对 $1000000007\left(10^{9}+7\right)$ 取模。

输入格式

第一行一个整数 $t$ ，表示数据组数。接下来 $t$ 行，每行一个整数 $n$ ，意义如题。

输出格式

一行一个整数表示答案模 $10^{9}+7$ 。

输入样例1

2
4
100000

输出样例1

2
980784195

数据范围

对于其中 $10 \%$ 的数据， $\mathrm{t}<=10, \mathrm{n}<=10$ 对于其他 $90 \%$ 的数据， $\mathrm{t}<=1, \mathrm{n}<=10^{\wedge} 6$