차량 배치

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

김 중위는 시가행진을 시작하기 전에 동원된 차량을 여러 지점에 적절히 배치할 수 있다. 단, 최소 한 대의 차량은 동원해야 하며, 배치가 가능하다면 더 많이 동원할 수 있다. 지점은 총 $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$로 나눈 나머지를 출력한다.