16041번 - Double Clique 다국어

문제

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⁹ + 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 ≤ n, m ≤ 2 × 10⁵), 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 ≤ a < b ≤ 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⁹ + 7.

제한

힌트