MOG
Spanish
|
English

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

MOG Training #7

Ended

B - Double Clique

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

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 of a graph is a graph with all of the same nodes, but if there’s no edge between nodes $a$ and $b$ in $G$, then there is an edge between $a$ and $b$ in $G'$, and if there is an edge between $a$ and $b$ in $G$, then there is no edge between $a$ and $b$ in $G'$.

A Clique is a subset of nodes that have an edge between every pair. A subset of nodes $S$ is called a Double Clique if $S$ forms a clique in $G$, and $V - S$ forms a clique in $G'$. Note that an empty set of nodes is considered a clique. Given a graph, count the number of double cliques in the graph modulo $10^9 + 7$.

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will begin with a line with two integers $n$ and $m$ $(1 \leq n, m \leq 2 \times 10^5)$, where $n$ is the number of nodes and $m$ is the number of edges in the graph. The nodes are numbered $1..n$. Each of the next $m$ lines will contain two integers $a$ and $b$ $(1 \leq a \lt b \leq n)$, representing an edge between nodes $a$ and $b$. The edges are guaranteed to be unique.

Output

Output a single integer, which is the number of Double Cliques in the graph modulo $10^9 + 7$.

Sample test(s)

Input
3 3 1 3 1 2 2 3
Output
4