Counting Essentially Different Cycles in a Triangulated Convex Polygon

Given a convex polygon with (n) vertices and its triangulation, the vertices are labeled (1) through (n) in clockwise order. In particular, the boundary edges connecting vertex (i) and vertex ((i \bmod n)+1) are implicitly present. In addition, the triangulation provides exactly (n-3) diagonal edges. These edges (both boundary and diagonals) form an undirected graph.

A simple cycle of length (m) (with (m \ge 3)) is defined as a sequence (a_0,a_1,\cdots,a_{m-1}) satisfying:

• \(1 \le a_i \le n\) for all \(i\).
• All vertices in the cycle are distinct (i.e. \(a_i \neq a_j\) whenever \(i \neq j\)).
• For every \(i\), there is an edge between \(a_i\) and \(a_{(i+1) \bmod m}\) in the graph.

Two cycles are considered essentially identical if one can be obtained from the other by a cyclic shift and/or a reversal (possibly combined with a cyclic shift).

Your task is to count the number of essentially different simple cycles in the graph, and output the answer modulo (10^9+7).

Note: Although the triangulation is provided only for (n \ge 4) (with (n-3) diagonals), the case (n=3) (a triangle) is valid and the only cycle is the boundary itself.

inputFormat

The first line contains an integer (n) representing the number of vertices of the convex polygon. For (n \ge 4), the next (n-3) lines each contain two integers (u) and (v), indicating a diagonal edge in the triangulation. For (n=3) there are no additional lines. The boundary edges between vertex (i) and vertex ((i \bmod n)+1) are implicitly present.

outputFormat

Output a single integer: the number of essentially different simple cycles in the graph, taken modulo (10^9+7).

sample

4
1 3

3