Good Edge Coloring

Given a directed acyclic graph \(G=(V,E)\) with \(|V|=N\) and \(|E|=M\), where every edge \((u,v)\in E\) satisfies \(u < v\). A coloring scheme is defined by assigning a weight of either \(0\) or \(1\) to each edge.

For an edge \((u,v)\), let \(w(u,v)\) denote its weight. A path from node \(u\) to node \(v\) is a sequence of vertices \( (a_1, a_2, \dots, a_k) \) such that \(a_1 = u\), \(a_k = v\), and for every \(1 \le i

A coloring scheme is called good if and only if for every pair of nodes \((u,v)\), all possible paths from \(u\) to \(v\) have the same weight modulo \(2\). In other words, for every pair \((u,v)\) and for any two paths \(P\) and \(Q\) from \(u\) to \(v\), it must hold that \[ \left( \sum_{e \in P} w(e) \right) \equiv \left( \sum_{e \in Q} w(e) \right) \pmod{2}. \]

You are required to count the number of good coloring schemes modulo \(10^9+7\).

Observation: A good coloring scheme is exactly one that can be induced by assigning each vertex \(f(v)\) a potential value in \(\{0,1\}\) such that for every edge \((u,v)\), \[ w(u,v) \equiv f(v) - f(u) \pmod{2}. \] Since subtraction modulo \(2\) is equivalent to addition, the condition can also be written as \(w(u,v) = f(u) + f(v)\) in \(\mathbb{F}_2\). With this formulation, the parity along any path from \(u\) to \(v\) is simply \(f(v)-f(u)\) (or equivalently, \(f(u)+f(v)\)).

However, note that if two vertices are connected in the underlying undirected graph, the potentials that differ by a global flip (i.e. \(f\) and \(1-f\)) will yield the same edge weights. Thus, if the underlying undirected graph has \(c\) connected components, then the number of distinct good coloring schemes is \[ 2^{N-c} \pmod{10^9+7}. \]

inputFormat

The first line contains two integers \(N\) and \(M\) representing the number of vertices and edges respectively. The following \(M\) lines each contain two integers \(u\) and \(v\) (1-indexed) representing a directed edge from \(u\) to \(v\) and satisfying \(u < v\).

outputFormat

Output a single integer, the number of good coloring schemes modulo \(10^9+7\).

sample

2 1
1 2

2