Two fools are walking down the street...

First fool: I've thought of a great problem. So, you have a directed acyclic graph, or DAG... and you want to assign a weight of 0 or 1 to each edge, such that between any two nodes, the weight of the path between them does not depend on the choice of the path...

Second fool: Hmm... but what if there is no path between some two nodes?

First fool: Well, sure, when there are multiple paths, they all have the same weight. Anyway, the goal is to find the number of such weight assignments.

Second fool: Yes, a good problem...

Fortunately, they then met their friend, a non-fool.

Non-fool: You surely don't know how to solve this, in other words, you're clueless. But I know how to solve a slightly simpler problem. I cannot require that the distance between nodes is independent of the path choice, but I can require that the distance modulo 2 is independent...

First and second fool: orz

Formally, you are given a directed graph with $N$ nodes and $M$ edges. The nodes are labeled with numbers from 1 to $N$, and for every directed edge $(u, v)$, it holds that $u < v$. A coloring of edges is an assignment of a value 0 or 1 to each edge. We denote the value of an edge $(u, v)$ as $w(u, v)$.

A path between nodes $u$ and $v$ is any sequence of nodes $(a_1, \dots, a_k)$ such that $a_1 = u$ and $a_k = v$. Also, for every $i$ between 1 and $k-1$, there exists an edge $(a_i, a_{i+1})$. The weight of the path is the sum of the weights of all edges on it, i.e., $w(a_1, a_2) + \dots + w(a_{k-1}, a_k)$.

A coloring $w$ is good if for every pair of nodes $(u, v)$ and for every pair of paths between them, the weights of these two paths have the same remainder when divided by 2.

Since the number of good colorings can be large, output its remainder when divided by $10^9 + 7$.

Input

The first line contains the natural numbers $N$ and $M$.

The next $M$ lines contain distinct pairs of numbers $u$ and $v$ ($1 \le u < v \le N$) which represent the edges of the graph.

Output

In a single line, output the remainder of the number of good colorings when divided by $10^9 + 7$.

Subtasks

In all subtasks, $1 \le N \le 400$ and $0 \le M \le 400$.

Examples

Input 1

4 4
1 2
2 3
3 4
1 4

Output 1

8

Input 2

4 4
1 3
1 4
2 3
2 4

Output 2

16

Note

Explanation of the first example:

The paths 1->2->3->4 and 1->4 must have the same weights modulo 2. If we assign weight 0 to the edge (1, 4), an even number of the remaining edges must have weight 1, which gives 4 combinations. If we assign weight 1 to the edge (1, 4), an odd number of the remaining edges must have weight 1, which again gives 4 combinations.