Є $N$ міст і $M$ двосторонніх доріг. Міста пронумеровано від $1$ до $N$, а дороги — від $1$ до $M$. Дорога $i$ з'єднує міста $A_i$ та $B_i$, а її довжина дорівнює $2^i$. Гарантується, що цими дорогами можна дістатися з будь-якого міста до будь-якого іншого.

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

Вхідні дані

Формат вхідних даних:

$$ \begin{gathered} N\quad M \\ A_1\quad B_1 \\ \vdots \\ A_M\quad B_M \end{gathered} $$

• $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$.