Terdapat $N$ kota dan $M$ jalan dua arah. Kota-kota diberi nomor dari $1$ hingga $N$, dan jalan-jalan diberi nomor dari $1$ hingga $M$. Jalan $i$ menghubungkan kota $A_i$ dan $B_i$, dan panjangnya adalah $2^i$. Dijamin bahwa setiap kota dapat dicapai dari kota mana pun menggunakan jalan-jalan ini.

Snuke ingin berkendara. Ia ingin berangkat dari kota $1$, melewati setiap jalan setidaknya sekali, lalu kembali ke kota $1$. Hitung panjang rute terpendek yang mungkin, modulo $10^9 + 7$.

Masukan

$$ \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$
• Setiap kota dapat dicapai dari kota mana pun menggunakan jalan-jalan tersebut.
• Tidak ada dua jalan yang menghubungkan pasangan kota yang sama.

Keluaran

Cetak panjang rute Snuke terpendek yang mungkin, modulo $10^9 + 7$.

Contoh

Masukan 1

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

Keluaran 1

70

Masukan 2

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

Keluaran 2

2132

Catatan

Sebagai contoh, pada contoh 1, salah satu rute optimal adalah $1 \to 2 \to 3 \to 4 \to 2 \to 3 \to 1$.