C. Clique Challenge
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

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

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.

Examples
Input
3 2
1 2
2 3
Output
5
Input
3 3
1 2
1 3
2 3
Output
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\}$$$.