Independent Sets

Limits: 2 sec., 256 MiB

You are given a graph \(G=(V,E)\), \(V\) represents the set of vertices and \(E\) represents the set of edges. A set of vertices is called independent set if any two vertices from the set do not share an edge. By convention the empty set is also considered as an independent set. In the following figure, the left figure represents the original graph and the right figure represents an independent set (nodes with black color) on that graph.

Computing the number of independent sets is a research interest and it is known that computing this quantity is in general computationally hard (NP). However, we will try to compute this function for graphs having restricted nature.

In this problem, we have set of vertices \(V = \{1,2, \dots N\}\) and number of edges is \(M\). The restriction is that an edge can occur between vertex \(i\) and vertex \(j\) only if \(|i-j| \leq 10\). Your task is computing the number of independent sets.

Input

The first line of the input consists of two integers \(N\) and \(M\).

Next \(M\) lines contain two integers each which are the indices (1-based) of the vertices that are connected with an edge. It is guaranteed that each edge satisfies the restriction mentioned above.

Output

Print one integer, the number of independent sets modulo \(10^9+7\).

Constraints

\(1 \le \mathbf{N} \le 10000\),

\(0 \le \mathbf{M} \le 100000\).

Samples

Input (stdin) сopy	Output (stdout) сopy
12 17 1 2 1 4 2 3 2 5 3 6 4 5 4 7 5 6 5 8 6 9 7 8 7 10 8 9 8 11 9 12 10 11 11 12	227

Input (stdin) сopy	Output (stdout) сopy
5 5 1 2 2 3 2 4 3 4 4 5	12

Notes

For the second sample independent sets are \(\emptyset,\) \(\{1\},\) \(\{2\},\) \(\{3\},\) \(\{4\},\) \(\{5\},\) \(\{1,3\},\) \(\{1,4\},\) \(\{1,5\},\) \(\{2,5\},\) \(\{3,5\},\) \(\{1,3,5\}\).