Vehicle Placement

Ahead of this year's Armed Forces Day, a parade through the city is also planned. First Lieutenant Kim commands the vehicles mobilized for the parade and must plan where they wait before entering it.

Before the parade starts, Lt. Kim can place the mobilized vehicles at several locations. At least one vehicle must be mobilized, and more can be mobilized if the locations allow it. There are $N$ locations, numbered 1 through $N$, and each location holds at most one vehicle. The locations are connected by $M$ bidirectional roads, and crossing one road takes 1 minute. The parade starts at location 1, and the only way in is through location 1. A vehicle can also be placed at location 1.

Once placement is finished, the vehicle at location 1 immediately enters the parade and disappears, and every other vehicle starts moving toward location 1. All vehicles move at the same speed along a shortest path. If there are several shortest paths, a vehicle follows the one whose next vertex has the smallest number. A vehicle that reaches location 1 safely enters the parade right after and disappears. If two vehicles reach the same location at the same time, including location 1, they collide.

Given the roads between the locations, find the number of vehicle placements with no collisions, modulo $1\,000\,000\,007 (= 10^{9} + 7)$. $1\,000\,000\,007$ is prime.

The first line contains the number of locations $N$ and the number of roads $M$, separated by a space. $(1 \le N \le 200\,000$; $N-1 \le M \le \min(\frac{N(N-1)}{2}, 200\,000))$

The next $M$ lines each contain two integers $a$ and $b$, separated by a space, which are the two different locations connected by a road. $(1 \le a,b \le N$; $a \neq b)$

Any two locations are connected by at most one road. Every location can reach location 1.

Print the number of vehicle placements with no collisions, modulo $1\,000\,000\,007$.