题目描述

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

输入格式

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 < b \leq n$), representing an edge between nodes $a$ and $b$. The edges are guaranteed to be unique.

输出格式

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

3 3
1 3
1 2
2 3

4