Problem Statement
Given are
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 all these costs are integers between 1 and L, inclusive.
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:
- LineMST
- Method:
- count
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int count(int N, int L)
- (be sure your method is public)
Constraints
- N will be between 2 and 200, inclusive.
- L will be between 1 and 200, inclusive.
Examples
3
2
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
10
Returns: 10
There are 10 beautiful graphs and f(G) is 1 for each of them.
3
1
Returns: 3
Now there is only one beautiful graph. As we already explained in Example 0, this graph has 3 MSTs and each of those is a line.
8
41
Returns: 655468587
200
200
Returns: 152699064
200
1
Returns: 861239556
200
2
Returns: 681666466
200
17
Returns: 99774264
200
100
Returns: 338549153
200
199
Returns: 823249413
199
200
Returns: 127066309
198
200
Returns: 312928197
199
199
Returns: 230595802
2
1
Returns: 1
2
2
Returns: 2
2
100
Returns: 100
130
30
Returns: 684102113
12
63
Returns: 797018408
9
37
Returns: 117160957
105
7
Returns: 60336279
137
83
Returns: 663692243
191
20
Returns: 766633940
128
4
Returns: 804757365
161
58
Returns: 304141530
176
33
Returns: 914220723
14
56
Returns: 802599361
71
84
Returns: 20099910
192
1
Returns: 194555441
93
5
Returns: 65098639
187
90
Returns: 767367751
108
40
Returns: 172447165
13
88
Returns: 603236712
115
68
Returns: 670925797
102
67
Returns: 347527363
131
79
Returns: 460277023
195
34
Returns: 333395286