트리

트리는 방향이 없는 그래프 중에서 어떤 두 정점을 잇는 경로가 정확히 하나인 그래프다. 다시 말해 모든 정점이 서로 연결되어 있고 사이클이 없는 그래프다.

서로 구별되는 정점 $N$개로 트리를 만드는 경우의 수를 생각해 보자. 정점에 $1$부터 $N$까지 번호를 붙이면, 간선이 어떤 두 정점을 잇는지에 따라 경우를 구분할 수 있다. 예를 들어 $N = 4$이면 아래 그림처럼 트리가 16가지다.

서로 구별되는 정점 $N$개로 만든 트리 중에서 주어진 간선 $M$개를 모두 포함하는 트리의 개수를 구하는 프로그램을 작성하라.

첫째 줄에 트리의 정점 개수 $N$과 포함해야 하는 간선의 개수 $M$이 공백으로 구분되어 주어진다. 이어지는 $M$개의 줄에는 포함해야 하는 간선의 양 끝 정점 $a$, $b$ ($1 \le a, b \le N$)가 주어진다. $a$와 $b$는 서로 다른 수이며, 같은 간선이 여러 번 주어지는 일은 없다. 주어진 간선을 모두 포함하는 트리를 만들지 못할 수도 있다.

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

주어진 간선을 모두 포함하는 트리의 개수를 출력한다. 이 수가 매우 커질 수 있으므로 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

위 그림에서 정점 1과 정점 2를 잇는 간선을 빨간색으로 칠했다. 정점이 4개일 때 이 간선을 포함하는 트리는 8개뿐이다.