Beculețe de brad

Cerință

Alice Elice s-a gândit să-i ofere lui Bob Glob câteva cadouri de Crăciun. Un cadou este un șir de beculețe de brad colorate roșu ($\color{#FF3131}{\text{R}}$) sau albastru ($\color{cyan}{\text{A}}$) de lungime $N$. Un cadou bun respectă $M$ condiții de tipul $(i, j)$ care înseamnă că becul $i$ are o culoare diferită față de becul $j$.

Din păcate Alice Elice e la shopping și nu are timp să calculeze câte cadouri bune diferite poate să-i cumpere lui Bob Glob.

Date de intrare

Pe prima linie se află $T$, reprezentând numărul de scenarii ale problemei. Structura unui scenariu este următoarea: pe prima linie se află $N$ și $M$, apoi pe următoarele $M$ linii se află două numere $i$ și $j$.

Date de ieșire

Pentru fiecare scenariu, afișați numărul cerut de Alice pe câte o linie, modulo $10^9 + 7$. Dacă nu există astfel de cadouri afișați mesajul Doar carbuni.

Restricții și precizări

• $1 \leq T \leq 10^2$
• $1 \leq N \leq 10^5$
• $0 \leq M \leq 10^5$
• Suma valorilor lui $N$ peste toate cele $T$ scenarii este de cel mult $5 \cdot 10^6$.
• Suma valorilor lui $M$ peste toate cele $T$ scenarii este de cel mult $10^6$.

Exemplul 1

stdin

1
5 3
1 2
2 3
4 5

stdout

4

Explicație

Cele $4$ cadouri bune sunt:
$\color{#FF3131}{\text{R}} \color{cyan}{\text{A}} \color{#FF3131}{\text{R}} \color{#FF3131}{\text{R}} \color{cyan}{\text{A}}$
$\color{#FF3131}{\text{R}} \color{cyan}{\text{A}} \color{#FF3131}{\text{R}} \color{cyan}{\text{A}} \color{#FF3131}{\text{R}}$
$\color{cyan}{\text{A}} \color{#FF3131}{\text{R}} \color{cyan}{\text{A}} \color{#FF3131}{\text{R}} \color{cyan}{\text{A}}$
$\color{cyan}{\text{A}} \color{#FF3131}{\text{R}} \color{cyan}{\text{A}} \color{cyan}{\text{A}} \color{#FF3131}{\text{R}}$

Exemplul 2

stdin

2
5 2
1 2
1 3
3 3
1 2
2 3
3 1

stdout

8
Doar carbuni

Explicație

• În primul exemplu cele $8$ cadouri bune sunt:
  $\color{#FF3131}{\text{R}} \color{cyan}{\text{A}} \color{cyan}{\text{A}} \color{#FF3131}{\text{R}} \color{cyan}{\text{A}}$
  $\color{#FF3131}{\text{R}} \color{cyan}{\text{A}} \color{cyan}{\text{A}} \color{cyan}{\text{A}} \color{#FF3131}{\text{R}}$
  $\color{cyan}{\text{A}} \color{#FF3131}{\text{R}} \color{#FF3131}{\text{R}} \color{#FF3131}{\text{R}} \color{cyan}{\text{A}}$
  $\color{cyan}{\text{A}} \color{#FF3131}{\text{R}} \color{#FF3131}{\text{R}} \color{cyan}{\text{A}} \color{#FF3131}{\text{R}}$
  $\color{#FF3131}{\text{R}} \color{cyan}{\text{A}} \color{cyan}{\text{A}} \color{#FF3131}{\text{R}} \color{#FF3131}{\text{R}}$
  $\color{#FF3131}{\text{R}} \color{cyan}{\text{A}} \color{cyan}{\text{A}} \color{cyan}{\text{A}} \color{cyan}{\text{A}}$
  $\color{cyan}{\text{A}} \color{#FF3131}{\text{R}} \color{#FF3131}{\text{R}} \color{#FF3131}{\text{R}} \color{#FF3131}{\text{R}}$
  $\color{cyan}{\text{A}} \color{#FF3131}{\text{R}} \color{#FF3131}{\text{R}} \color{cyan}{\text{A}} \color{cyan}{\text{A}}$
• În cel deal doilea exemplu se poate demonstra că nu există soluție.