มีเมือง $N$ เมืองและถนนสองทิศทาง $M$ สาย เมืองมีหมายเลขตั้งแต่ $1$ ถึง $N$ และถนนมีหมายเลขตั้งแต่ $1$ ถึง $M$ ถนนสายที่ $i$ เชื่อมเมือง $A_i$ กับ $B_i$ และมีความยาว $2^i$ รับประกันว่าสามารถเดินทางจากเมืองใด ๆ ไปยังเมืองอื่นใดได้โดยใช้ถนนเหล่านี้

Snuke ต้องการขับรถเที่ยว เขาต้องการเริ่มต้นจากเมือง $1$ ผ่านถนนทุกสายอย่างน้อยหนึ่งครั้ง แล้วกลับมายังเมือง $1$ จงคำนวณความยาวที่สั้นที่สุดที่เป็นไปได้ของเส้นทางของเขา โดยหาค่าโมดูโล $10^9 + 7$

ข้อมูลนำเข้า

$$ \begin{array}{ll} 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 เส้นทางที่เหมาะสมที่สุดเส้นทางหนึ่งคือ $1 \to 2 \to 3 \to 4 \to 2 \to 3 \to 1$