Tree

Time limit1sMemory limit512 MB

Summary

Count labelled trees on N vertices that contain all M given edges, modulo 1e9+7, with N up to 1e9.

Level: Medium7 of 10
Topics: Combinatorics, Union-find, Math, Graph
Solved: No attempts yet

Problem

A tree is an undirected graph in which exactly one path connects any two vertices. Equivalently, it is a graph that is connected and has no cycle.

Count the trees you can build on $N$ distinguishable vertices. Number the vertices from $1$ to $N$ , and two trees are different when their edges join different pairs of vertices. For $N = 4$ there are 16 trees, shown below.

The 16 trees on 4 labelled vertices

Write a program that counts the trees on $N$ distinguishable vertices that contain all $M$ given edges.

Input

The first line contains two integers separated by a space: the number of vertices $N$ and the number of edges $M$ that the tree must contain. Each of the next $M$ lines contains the two endpoints $a$ and $b$ ( $1 \le a, b \le N$ ) of a required edge. The values $a$ and $b$ are different, and no edge is given twice. It may be impossible to build a tree that contains every given edge.

$1 \le N \le 10^9$ , $0 \le M \le 10^5$

Output

Print the number of trees that contain every given edge. The number can be very large, so print it modulo $1\,000\,000\,007$ .

Hint

The trees on 4 labelled vertices with the edge between vertex 1 and vertex 2 in red

The picture colours the edge between vertex 1 and vertex 2 red. With 4 vertices, only 8 trees contain that edge.

Examples2

Example 1
Input
```
4 0
```
Expected output
```
16
```
Example 2
Input
```
4 1
1 2
```
Expected output
```
8
```