LineMSTDiv2 | Topcoder Archive

Problem Statement

Given is an int N.

A complete graph is a graph in which each pair of vertices is connected by exactly one undirected edge.

A graph is called beautiful if:

It is a complete graph on N vertices.
Each edge has an associated cost, and each of these costs is either 1 or 2.

Hence, there are exactly 2^(N*(N-1)/2) different beautiful graphs.

The minimum spanning tree (MST) of a beautiful graph is its subgraph with the following properties:

The subgraph contains all N vertices.
The subgraph is connected. (I.e., it is possible to get from any vertex to any other vertex using only edges that belong to the subgraph.)
The total cost of edges in the subgraph is as small as possible.

A single beautiful graph can have multiple MSTs. (Each of these MSTs will contain a different set of edges, but they will have the same total cost.)

An MST is called a line if the degree of each of its vertices is at most 2.

Hibiki likes MSTs. She also likes lines. For each beautiful graph G, let f(G) be the number of its MSTs that are lines. (Note that for some beautiful graphs it may be the case that f(G)=0.)

Let X be the sum of the values f(G) over all beautiful graphs G. Please calculate X for her. As X can be very large, compute and return the value (X modulo 1,000,000,007).

Definition

Class:: LineMSTDiv2
Method:: count
Parameters:: int
Returns:: int
Method signature:: int count(int N)
(be sure your method is public)

Constraints

N will be between 2 and 16, inclusive.

Examples

```
3
```
```
Returns: 15
```
Beautiful graphs are complete graphs on 3 vertices in which each edge has cost either 1 or 2. There are 8 such graphs. Some of these graphs have more than one MST. For example, the graph in which each edge has cost 1 has three different MSTs. In this case, each of those three MSTs is a line, so we count each of them.
```
2
```
```
Returns: 2
```
There are only 2 beautiful graphs. The value of f is 1 for both graphs, so the answer is 2.
```
16
```
```
Returns: 682141922
```
Don't forget to take modulo.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.