== include(page="template/taskheader" task_id="influencer") ==

Poveste şi cerinţă...

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) % N$ (unde $0 ≤ i ≤ 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) % N$.
* $L$: Comunicare directă unidirecţională de la $(i + 1) % N$ la $i$.
* $R$: Comunicare directă unidirecţională de la $i$ la $(i + 1) % N$.
* $B$: Comunicare directă bidirecţională între $i$ şi $(i + 1) % N$.
 
h2. 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$.

h2. Date de intrare

Fişierul de intrare $influencer.in$ ...

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$.

h2. Date de ieşire

În fişierul de ieşire $influencer.out$ ...

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$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $3 ≤ N ≤ 1 000 000$
* $0 ≤ M ≤ [N/2]$, unde [x] reprezintă parte întreagă din x
* Pentru orice legătură specială $(u, v)$, se garantează că $|u - v| ≥ 2$ şi perechea nu este $(0, N - 1)$ (nodurile nu sunt adiacente pe cerc).
 
table(example). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $11$ | $N ≤ 10$ şi corzile nu se pot intersecta în capete|
| $2$ | $16$ | $M = 0$|
| $3$ | $9$ | $M = 1$|
| $4$ | $4$ | Toate corzile au unul dintre capete în influencerul $0$ |
| $5$ | $17$ |$N ≤ 1 000$ şi corzile nu se pot intersecta în capete |
| $6$ | $29$ | Corzile nu se pot intersecta în capete |
| $7$ | $14$ | Fără alte restricţii |

h2. Exemplu
table(example). |_. influencer.in |_. influencer.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 1
0 2
| 81

|
h3. Explicaţie

...

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 → 1$ şi $1 → 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 * 9 = 81$.

== include(page="template/taskfooter" task_id="influencer") ==