Есть $N$ городов и $M$ двусторонних дорог. Города пронумерованы от $1$ до $N$, а дороги — от $1$ до $M$. Дорога $i$ соединяет города $A_i$ и $B_i$, а её длина равна $2^i$. Гарантируется, что по этим дорогам можно добраться из любого города в любой другой.

Snuke хочет покататься на машине. Он хочет начать в городе $1$, проехать по каждой дороге хотя бы один раз и вернуться в город $1$. Вычислите минимально возможную длину его маршрута по модулю $10^9 + 7$.

Входные данные

$$ \begin{array}{cc} N & M\\ A_1 & B_1\\ \vdots & \\ A_M & B_M \end{array} $$

• $2 \le N \le 400000$
• $1 \le M \le 500000$
• $1 \le A_i, B_i \le N$
• $A_i \ne B_i$
• По дорогам можно добраться из любого города в любой другой.
• Никакие две дороги не соединяют одну и ту же пару городов.

Выходные данные

Выведите минимально возможную длину маршрута Snuke по модулю $10^9 + 7$.

Примеры

Входные данные 1

4 5
1 2
3 4
2 3
1 3
2 4

Выходные данные 1

70

Входные данные 2

6 10
4 6
4 5
3 6
5 2
3 2
1 2
3 4
6 1
2 4
1 3

Выходные данные 2

2132

Примечание

Например, в первом примере один из оптимальных маршрутов — $1 \to 2 \to 3 \to 4 \to 2 \to 3 \to 1$.