Double Clique

Time limit2sMemory limit512 MB

Summary

Count the subsets S that are cliques in G while the remaining vertices have no edges among them in G, modulo 1e9+7, for a graph with up to 2e5 nodes.

Level: Medium7 of 10
Topics: Graph, Combinatorics, Implementation
Solved: No attempts yet

Problem

You are given an undirected graph $G$ with $n$ nodes and $m$ edges. The set of vertices is $V$ and the set of edges is $E$ .

Let the complement of $G$ be $G'$ . The complement has all the same nodes, but if there is no edge between nodes $a$ and $b$ in $G$ , then $G'$ has an edge between $a$ and $b$ . If $G$ has an edge between $a$ and $b$ , then $G'$ has no edge between them.

A clique is a subset of nodes where every pair has an edge. A subset of nodes $S$ is a double clique if $S$ is a clique in $G$ and $V - S$ is a clique in $G'$ . The empty set counts as a clique.

Given the graph, count the double cliques modulo $10^9 + 7$ .

Input

The first line has two integers $n$ and $m$ ( $1 \le n, m \le 2 \times 10^5$ ). Each of the next $m$ lines has two integers $a$ and $b$ ( $1 \le a < b \le n$ ), meaning there is an edge between nodes $a$ and $b$ . All edges are unique.

Output

Print a single integer, the number of double cliques modulo $10^9 + 7$ .

Examples1

Example 1
Input
```
3 3
1 3
1 2
2 3
```
Expected output
```
4
```