U573139 排列计数

给定一个正整数 $n$，求满足以下条件的排列 $a$ 的数量： - 长度为 $n$。 - 对于每个满足 $1\le i\le n$ 的 $i$，$i\times a_i$ 为完全平方数。 求输出答案对 $10^9+7$ 取模的结果。

第一行一个正整数 $T$，代表问题个数。 接下来 $T$ 行，每行一个正整数 $n$，具体含义见题目描述。

输出 $T$ 行，每行一个正整数，代表满足条件的排列数对 $10^9+7$ 取模的结果。

【样例解释 1】 容易证明只有 $\{1,2,3,4\}$ 和 $\{4,2,3,1\}$ 两组满足条件。 --- 【数据范围】 - Subtask 0（5 pts）$1\le \sum n\le10$。 - Subtask 1（25 pts）：$T=1$。 - Subtask 3（70 pts）：无特殊性质。 对于全部数据，保证 $1\le n\le 5\times10^6$，$1\le T\le 10^6$。