你有 $n$ 个点，你可以在这 $n$ 个点之间连无向边，两个点之间至多只能连一条边，也不允许连自环，问至多能连多少条边。
但这个问题的答案显然是 $\displaystyle \frac{n(n-1)}{2}$ 条。所以有一个额外的限制，要求这个图不存在非平凡的自同构。一个图 $G$ 有非平凡的自同构定义为存在一个 $1, 2, \ldots, n$ 的置换 $p_1, p_2, \ldots ,p_n$ 满足对于所有点 $u, v$，$(u, v)$ 之间有边当且仅当 $(p_u, p_v)$ 之间有边，并且这个置换非平凡也就是存在一个点 $u$ 使得 $p_u \ne u$。
- 比如对于一个 $5$ 个点的图 $(1,2),(2,3),(3,4),(4,5),(5,1),(1,3)$，那么 $p_1=3, p_2=2, p_3=1, p_4=5, p_5=4$ 为这个图的一个非平凡的自同构。
你要回答一个 $n$ 个点的无向简单的不存在非平凡自同构的图最多有多少条边，如果答案不存在，即不存在 $n$个点满足条件的图，请输出 -1，否则输出答案对 $10^9+7$ 的余数。
输入格式
第一行一个正整数 $T$ 表示数据组数。
接下来 $T$ 行，每行一个正整数 $n$ 表示你要回答的图的点的个数。
输出格式
共 $T$ 行，每行输出 -1 或者答案对 $10^9+7$ 的余数。
样例数据
样例输入
6
1
2
3
4
5
6样例输出
0
-1
-1
-1
-1
9子任务
| 测试点 | $T \leq$ | $n \leq $ |
|---|---|---|
| $1$ | $10$ | $10$ |
| $2$ | ||
| $3$ | $100$ | $100$ |
| $4$ | ||
| $5$ | $10^4$ | $10^5$ |
| $6$ | ||
| $7$ | $10^9$ | |
| $8$ | ||
| $9$ | $10^{18}$ | |
| $10$ | $1$ | $10^{100}$ |