Graph Expansion and Accumulation

Bessie, looking to broaden her mathematical knowledge, has enrolled in a graph theory course. However, she found herself stuck on the following problem:

Given a connected undirected graph with (N) vertices numbered (1,2,\dots,N) and (M) edges numbered (1,2,\dots,M) (with (2 \le N \le 2\cdot10^5) and (N-1 \le M \le 4\cdot10^5)). The following process is executed:

1. Initialize the set (S = {1}) (starting from vertex 1) and a variable (h = 0).
2. While (|S| < N), repeat:
   1. Among all edges which connect a vertex in (S) to a vertex not in (S) (i.e. edges where exactly one endpoint is in (S)), choose the edge with the smallest index, say (e).
   2. Add the vertex (of the chosen edge) which is not in (S) to (S).
   3. Update (h) as follows: (h \gets 10h + e).
3. Output (h \bmod (10^9+7)).

Your task is to simulate this process and output the final value of (h \bmod (10^9+7)). Note that the graph is guaranteed to be connected, and the process will always add exactly one new vertex per iteration until all vertices are included.

inputFormat

The first line contains two integers (N) and (M) separated by a space. The following (M) lines each contain two integers (u) and (v), representing an undirected edge between vertices (u) and (v).

outputFormat

Print a single integer representing the final value of (h \bmod (10^9+7)).

sample

2 1
1 2

1