Counting Graphs with Constrained Bridges

You are given two integers n and m. Consider all undirected simple graphs (i.e. no multi‐edges and no self-loops) on n labeled vertices that are connected. An edge in a connected graph is called a bridge (or cut edge) if removing that edge increases the number of connected components. In other words, if deleting an edge disconnects the graph, then that edge is a bridge.

Your task is to count the number of connected graphs on n vertices (with vertex labels 1, 2, …, n) such that the total number of bridges in the graph is at most m. Since the answer can be very large, output it modulo \(10^9+7\).

Note: A graph is simple if it does not have self-loops or multiple edges.

Definition (Bridge): In a connected graph \(G = (V, E)\), an edge \(e \in E\) is called a bridge if \(G \setminus \{e\}\) is disconnected.

inputFormat

The input consists of a single line containing two space-separated integers:

• n (the number of vertices)
• m (the maximum allowed number of bridges)

You may assume that n is small (e.g. \(n \le 6\)) so that all graphs on n labeled vertices can be enumerated.

outputFormat

Output a single integer — the number of connected graphs satisfying the condition, taken modulo \(10^9+7\).

sample

2 0

0