influencer

Rețeaua socială Circle are $N$ influenceri, numerotați de la $0$ la $N - 1$, așezați sub forma unui cerc. În interiorul rețelei există $M$ legături speciale de comunicare bidirecțională, date sub forma unor perechi $(u, v)$. Aceste legături respectă o regulă strictă de securitate: dacă desenăm influencerii pe cerc și legăturile ca segmente (corzi) între ei, oricare două segmente nu se pot intersecta decât, eventual, în capete. De asemenea, legăturile speciale se pot forma doar între influenceri neadiacenți pe cerc.

CEO-ul rețelei dorește să configureze conexiunile de bază de pe conturul cercului. Pentru fiecare pereche de influenceri adiacenți $i$ și $(i + 1) \text{ mod } N$ (unde $0 \leq i \leq N - 1$), se alege un tip de conexiune, reprezentat printr-un caracter dintr-un șir de configurare $S$ de lungime $N$ (indexat de la $0$). Caracterul $S_i$ poate fi:

• N: Nu există comunicare directă între $i$ și $(i + 1) \text{ mod } N$.
• L: Comunicare directă unidirecțională de la $(i + 1) \text{ mod } N$ la $i$.
• R: Comunicare directă unidirecțională de la $i$ la $(i + 1) \text{ mod } N$.
• B: Comunicare directă bidirecțională între $i$ și $(i + 1) \text{ mod } N$.

Cerință

Să se determine numărul de moduri distincte de a construi șirul de configurare $S$ astfel încât în rețeaua rezultată, orice influencer să poată transmite un mesaj oricărui alt influencer, direct sau indirect, folosind conexiunile de pe cerc și legăturile speciale. Deoarece acest număr poate fi foarte mare, se cere afișarea lui modulo $10^9 + 7$.

Date de intrare

Fișierul de intrare influencer.in conține pe prima linie două numere naturale $N$ și $M$, separate printr-un spațiu. Pe următoarele $M$ linii se vor afla câte două numere naturale $u$ și $v$, separate printr-un spațiu, reprezentând o legătură specială bidirecțională între influencerul $u$ și $v$.

Date de ieșire

Fișierul de ieșire influencer.out va conține pe o singură linie un număr natural, reprezentând numărul de șiruri de configurare $S$ valide, modulo $10^9 + 7$.

Restricții și precizări

• $3 \leq N \leq 1 \ 000 \ 000$;
• $0 \leq M \leq \lfloor \frac{N}{2} \rfloor$;
• Pentru orice legătură specială $(u, v)$, se garantează că $|u - v| \geq 2$ și perechea nu este $(0, N - 1)$ (nodurile nu sunt adiacente pe cerc).

Exemplu

influencer.in

4 1
0 2

influencer.out

81

Explicații

Avem $N = 4$ influenceri și o singură legătură ($M = 1$) specială bidirecțională între influencerul $0$ și $2$. Această coardă împarte cercul în două jumătăți care devin independente din punct de vedere al conectivității față de ansamblul $\{0, 2\}$: calea prin utilizatorul $1$ și calea prin utilizatorul $3$.

Pentru ca întreaga rețea să fie tare conexă, este suficient și necesar ca influencerul $1$ și $3$ să poată trimite și primi mesaje de la mulțimea $\{0, 2\}$.

Să analizăm muchiile $S_0$ (între $0$ și $1$) și $S_1$ (între $1$ și $2$). Există exact $9$ perechi de caractere valide care asigură conectivitatea bidirecțională a nodului $1$ față de $\{0, 2\}$:

• BB, BR, BL, BN, RB, RR, LB, LL, NB.

De exemplu, dacă alegem perechea LL ($S_0 =$ L, $S_1 =$ L), fluxul este $2 \rightarrow 1$ și $1 \rightarrow 0$. Nodul $1$ primește de la $2$ și trimite la $0$. Deoarece $0$ și $2$ comunică direct prin coardă, nodul $1$ este perfect integrat în circuit. Orice altă combinație (de exemplu NN, RL, LR) va bloca fluxul nodului $1$ fie la primire, fie la trimitere.

În mod identic, pentru nodul $3$, muchiile de pe cealaltă jumătate a cercului, $S_2$ și $S_3$, pot fi alese tot în $9$ moduri valide.

Deoarece deciziile pentru jumătatea stângă sunt complet independente de cele pentru jumătatea dreaptă (datorită corzii centrale bidirecționale), numărul total de moduri pentru a construi șirul $S$ este $9 \times 9 = 81$.