module

Cerință

Se dă un graf neorientat cu $N$ noduri (numerotate de la $1$ la $N$) şi $M$ muchii. Vom defini $A(i,j) = 1$ dacă nodurile $i$ şi $j$ sunt adiacente (există o muchie între ele), respectiv $A(i,j) = 0$ dacă nodurile $i$ şi $j$ nu sunt adiacente.
O submulţime $S$ de noduri ale grafului se numeşte modul dacă îndeplineşte următoarea condiţie: oricare ar fi trei noduri $x$, $y$ si $z$ astfel incat $x \in S, y \in S$ si $z ∉ S$, avem $A(x, z) = A(y, z)$.
Mai exact, pentru orice nod $z$ din afara mulţimii $S$, ori toate nodurile din $S$ sunt adiacente cu $z$ ori niciun nod din $S$ nu este adiacent cu $z$. Câteva exemple simple de module sunt: mulţimea vidă, mulţimea tuturor nodurilor grafului, mulţimile ce constau din câte un singur nod al grafului.
Determinaţi numărul de module ale grafului dat, modulo $34949$.

Date de intrare

Prima linie a fişierului de intrare module.in conţine numerele întregi $N$ şi $M$, separate printr-un spaţiu. Următoarele $M$ linii conţin câte două numere întregi $i$ şi $j$, separate printr-un spaţiu, având semnificaţia că există o muchie între nodul $i$ şi nodul $j$ în graf.

Date de ieșire

În fişierul de ieşire module.out veţi afişa numărul de module ale grafului dat, modulo $34949$.

Restricții și precizări

• $1 \leq N \leq 100$
• $0 \leq M \leq \frac{N \cdot (N - 1)}{2}$
• $1 \leq i, j \leq N$
• $i \neq j$
• În fişierul de intrare nu se vor repeta muchii.

Exemplu

module.in

7 11
5 1
5 6
1 2
1 3
1 7
6 2
6 3
6 7
4 2
4 3
4 7

module.out

14

Explicație

Cele $14$ module sunt:
$\{\}, \{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}, \{7\}, \{1,6\}, \{2,3\}, \{2,7\}, \{3,7\}, \{2,3,7\}, \{1,2,3,4,5,6,7\}$.