توجد $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$.