题目描述

你有 $n$ 个点，你可以在这 $n$ 个点之间连无向边，两个点之间至多只能连一条边，也不允许连自环，问至多能连多少条边。

但这个问题的答案显然是 $\dfrac{n(n-1)}{2}$ 条。所以有一个额外的限制，要求这个图不存在非平凡的自同构。

一个图 $G$ 有非平凡的自同构定义为存在一个 $1$ 到 $n$ 的置换 $p(1)$ 到 $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$ 表示数据组数。
对于每组数据：
一个正整数 $n$ 表示你要回答的图的点的个数。

输出格式

对于每组数据：
一行一个整数代表答案对 $10^9+7$ 取模的结果，如果不存在 $n$ 个点满足条件的图，就输出 -1。

6
1
2
3
4
5
6

0
-1
-1
-1
-1
9

提示

对于 $100\%$ 的数据，$1 \le n \le 10^{100}$，$1 \le T \le 10^4$。