Clique Challenge
Description
A clique of a graph $G$ is a set $X$ of vertices of $G$ with the property that every pair of distinct vertices in $X$ are adjacent in $G$. You are given an undirected graph $G$ with $n$ vertices and $m$ edges, please find the number of distinct non-empty cliques of graph $G$.
The first line of the input contains two integers $n$ and $m$ ($1\leq n,m\leq 1\,000$), denoting the number of vertices and the number of edges.
Each of the following $m$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i,v_i\leq n$, $u_i\neq v_i$), describing an undirected edge between the $u_i$-th vertex and the $v_i$-th vertex.
It is guaranteed that there will be at most one edge between each pair of different vertices.
Print a single line containing an integer, denoting the number of cliques. Note that the answer may be extremely large, so please print it modulo $(10^9+7)$ instead.
Input
The first line of the input contains two integers $n$ and $m$ ($1\leq n,m\leq 1\,000$), denoting the number of vertices and the number of edges.
Each of the following $m$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i,v_i\leq n$, $u_i\neq v_i$), describing an undirected edge between the $u_i$-th vertex and the $v_i$-th vertex.
It is guaranteed that there will be at most one edge between each pair of different vertices.
Output
Print a single line containing an integer, denoting the number of cliques. Note that the answer may be extremely large, so please print it modulo $(10^9+7)$ instead.
3 2
1 2
2 3
3 3
1 2
1 3
2 3
5
7
Note
In the first example, cliques are $\{1\}$, $\{2\}$, $\{3\}$, $\{1,2\}$ and $\{2,3\}$.
In the second example, cliques are $\{1\}$, $\{2\}$, $\{3\}$, $\{1,2\}$, $\{1,3\}$, $\{2,3\}$ and $\{1,2,3\}$.