#4907. [BeiJing2017]同构

内存限制:256 MiB 时间限制:20 Sec

题目描述

你有n个点,你可以在这n个点之间连无向边,两个点之间至多只能连一条边,也不允许连自环,问至多能连多少条
边。但这个问题的答案显然是n(n-1)/2条。所以有一个额外的限制,要求这个图不存在非平凡的自同构。一个图G
有非平凡的自同构定义为存在一个1,2,...,n的置换p(1), p(2),...,p(n)满足对于所有点u, v,(u, v)之间有边当
且仅当(p(u), p(v))之间有边,并且这个置换非平凡也就是存在一个点u使得p(u) ≠ 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表示你要回答的图的点的个数。
本题只有一个点n=10^100
其余测试点n<=10^18

输出格式

共T行,每行输出 "-1" 或者答案对10^9+7的余数。

样例

样例输入


			
6
1
2
3
4
5
6

样例输出


			
0
-1
-1
-1
-1
9

数据范围与提示