ישנן $N$ ערים ו־$M$ דרכים דו־כיווניות. הערים ממוספרות מ־$1$ עד $N$, והדרכים ממוספרות מ־$1$ עד $M$. הדרך $i$ מחברת בין הערים $A_i$ ו־$B_i$, ואורכה הוא $2^i$. מובטח שאפשר להגיע מכל עיר לכל עיר באמצעות הדרכים האלה.

Snuke רוצה לצאת לנסיעה. הוא רוצה להתחיל בעיר $1$, לעבור בכל דרך לפחות פעם אחת ולחזור לעיר $1$. חשבו את האורך הקטן ביותר האפשרי של המסלול שלו, מודולו $10^9+7$.

קלט

$$ \begin{gathered} N\ M\\ A_1\ B_1\\ \vdots\\ A_M\ 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$ אחד המסלולים המיטביים הוא $1\to2\to3\to4\to2\to3\to1$.