Problem Statement
Given is an
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.
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.
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.
4
Returns: 204
5
Returns: 5880
6
Returns: 442440
7
Returns: 89008920
8
Returns: 730466899
9
Returns: 24355907
10
Returns: 383977177
11
Returns: 883376076
12
Returns: 615480608
13
Returns: 915018779
14
Returns: 222917234
15
Returns: 296399592