30206번 - 차량 배치

문제

올해 국군의 날의 행사에 시가행진 행사도 계획되었다. 그래서 시가행진에 동원된 차량을 통솔해야 하는 김 중위는 차들이 어디서 대기하다가 시가행진에 진입하게 할지를 계획하게 되었다.

김 중위는 시가행진을 시작하기 전, 시가행진에 동원된 차량을 여러 지점에 적절히 배치할 수 있다. 단, 최소 한 대의 차량이 동원되며, 배치가 가능하다면 더 동원할 수 있다. 차량의 배치가 가능한 지점들은 총 $N$개로, 1ドル$번부터 $N$번까지 번호들이 매겨져 있으며 각 지점에는 차량을 최대 한 대만 배치할 수 있다. 또한, $M$개의 양방향 도로들을 통해서 지점 사이를 이동할 수 있다. 하나의 도로를 지나는 데에 1ドル$분이 걸린다. 시가행진이 시작되는 장소는 1ドル$번 지점을 거쳐서만 들어갈 수 있으며, 1ドル$번 지점에도 차량을 배치할 수 있다.

차량의 배치가 끝나면 1ドル$번 지점에 있던 차량은 바로 시가행진 행사에 들어가서 사라지고, 모든 차량은 1ドル$번 지점으로 이동하기 시작한다. 이때, 모든 차량은 최단 경로를 통해 동일한 속도로 이동하며, 만약 최단 경로가 여러 가지라면 그 중 다음으로 가는 정점의 번호가 작은 경로를 따라 이동한다. 이후에 1ドル$번 지점에 무사히 도착한 차량은 직후 시가행진 행사에 들어가서 사라진다. 다만 두 차량이 같은 시간에 1ドル$번 지점을 포함한 같은 지점에 도달하면 충돌 사고가 난다.

김 중위를 도와서 지점들을 잇는 도로들이 주어졌을 때, 충돌 사고가 나지 않는 차량 배치 방법의 개수를 1ドル,000円,000円,007円(= 10^{9} + 7)$으로 나눈 나머지를 구해보자. 1ドル,000円,000円,007円$은 소수이다.

입력

첫 번째 줄에 지점의 개수 $N$과 도로의 개수 $M$이 공백으로 구분되어 정수로 주어진다. $(1 \le N \le 200,000円;$ $N-1 \le M \le \min(\frac{N(N-1)}{2}, 200,000円))$

이후 $M$개의 줄에 걸쳐 각 도로가 잇는 서로 다른 두 지점을 나타내는 정수 $a,ドル $b$가 공백으로 구분되어 정수로 주어진다. $(1 \le a,b \le N;$ $a \neq b)$

임의의 두 지점마다, 둘을 잇는 도로는 최대 하나이다. 또한, 모든 지점에서 1ドル$번 지점으로 이동할 수 있다.

출력

충돌 사고가 나지 않는 차량 배치 방법의 개수를 1ドル,000円,000円,007円$로 나눈 나머지를 출력한다.

제한

힌트