You are given an undirected graph that has \(n\) nodes and \(m\) edges.

We consider subgraphs that have all nodes of the original graph and some of its edges. A subgraph is called Eulerian if each node has even degree.

Your task is to count the number of Eulerian subgraphs modulo \(10^9+7\).

Input

• The first input line has two integers \(n\) and \(m\): the number of nodes and edges. The nodes are numbered \(1,2,\ldots,n\).
• After this, there are \(m\) lines that describe the edges. Each line has two integers \(a\) and \(b\): there is an edge between nodes \(a\) and \(b\). There is at most one edge between two nodes, and each edge connects two distinct nodes.

Output

• Print the number of Eulerian subgraphs modulo \(10^9+7\).

Constraints

• \(1 \leq n \leq 10 ^ 5\)
• \(0 \leq m \leq 2 \cdot 10 ^ 5\)
• \(1 \leq a, b \leq n\)

Example

Sample input

4 3
1 2
1 3
2 3

Sample output

2

Note

You can either keep or remove all edges, so there are two possible Eulerian subgraphs.