Maximum Edges in an Asymmetric Graph

You are given an integer n representing the number of vertices. You are allowed to add undirected edges between these n vertices under the restrictions that there is at most one edge between any two distinct vertices and no self‐loops. In a graph, a nontrivial automorphism is defined as a permutation p: {1,2,…,n} → {1,2,…,n} (with at least one vertex u such that p(u) ≠ u) that satisfies: for every pair of 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). A graph with no nontrivial automorphism is said to be asymmetric.

Although the maximum possible number of edges in a simple graph on n vertices is \(\frac{n(n-1)}{2}\), the complete graph always has many automorphisms. In this problem, we want a simple undirected graph on n vertices that is asymmetric, and among all such graphs, we wish to maximize the number of edges.

You are to output the maximum number of edges in such an asymmetric graph. If no asymmetric graph exists on n vertices, output -1. It can be shown that:

• For n = 1: the only graph (with 0 edges) is asymmetric.
• For n = 2,3,4,5: no asymmetric graph exists.
• For n = 6: the maximum number of edges in an asymmetric graph is 8.
• For n \ge 7: one may construct an asymmetric graph by taking the complete graph \(K_n\) and deleting an asymmetric spanning tree. Since an asymmetric spanning tree exists for every n \ge 7 and a spanning tree has exactly n-1 edges, the maximum number of edges is \[ \frac{n(n-1)}{2} - (n-1) = \frac{n^2 - 3n + 2}{2} = \frac{(n-1)(n-2)}{2}. \]

Since the answer can be very large, output it modulo \(10^9+7\).

inputFormat

The input consists of a single integer n representing the number of vertices.

outputFormat

Output a single integer representing the maximum number of edges in an asymmetric graph on n vertices, modulo \(10^9+7\). If no such graph exists, output -1.

sample

1

0