同构 - Problem Detail

ID: 3563

Type: RemoteJudge

1000ms

256MiB

Difficulty: (None)

Uploaded By:

No submission language available for this problem.

题目描述

你有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的余数。

0
-1
-1
-1
-1
9