P3993 [BJOI2017] Isomorphism

You have $n$ vertices. You may add undirected edges between these $n$ vertices, with at most one edge per pair and no self-loops. What is the maximum number of edges you can add? The obvious answer is $\dfrac{n(n-1)}{2}$ edges. Therefore, there is an additional constraint: the graph must not have a nontrivial automorphism. A graph $G$ has a nontrivial automorphism if there exists a permutation $p$ of $\{1, \dots, n\}$ such that for all vertices $u, v$, there is an edge between $u$ and $v$ if and only if there is an edge between $p(u)$ and $p(v)$, and this permutation is nontrivial, i.e., there exists a vertex $u$ with $p(u) \ne u$. For example, for the 5-vertex graph $(1,2),(2,3),(3,4),(4,5),(5,1),(1,3)$, the mapping $p(1)=3$, $p(2)=2$, $p(3)=1$, $p(4)=5$, $p(5)=4$ is a nontrivial automorphism of this graph. You need to answer: among simple undirected graphs on $n$ vertices that have no nontrivial automorphism, what is the maximum number of edges? If no such graph on $n$ vertices exists, output `-1`; otherwise, output the answer modulo $10^9+7$.

**This problem contains multiple test cases.** A single line with a positive integer $T$, the number of test cases. For each test case: A single positive integer $n$, the number of vertices.

For each test case: Output a single integer, the answer modulo $10^9+7$. If no graph on $n$ vertices satisfies the condition, output `-1`.

| Test point | Constraints | |:-:|:-:| | $1$ | $n, T \le 6$ | | $2$ | $n, T \le 10$ | | $3,4$ | $n, T \le 100$ | | $5,6$ | $n \le 10^5$ | | $7,8$ | $n \le 10^9$ | | $9$ | $n \le 10^{18}$ | | $10$ | $n=10^{100}$ | For $100\%$ of the testdata, $1 \le n \le 10^{100}$, $1 \le T \le 10^4$. Translated by ChatGPT 5