Problem Background

Translated from Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection) D1T3. $\texttt{0.5s,1G}$.

Problem Description

Given a directed graph \( G = (V, E) \), where \( |V| = N \) and \( |E| = M \), such that for all \( (u, v) \in E \), \( u < v \).

A coloring scheme for the edges is a method of assigning \( 0/1 \) weights to each edge. Let the weight of edge \( (u, v) \) be \( w(u, v) \).

A path from node \( u \) to \( v \) is a sequence \( (a_1, a_2, \cdots, a_k) \) such that \( a_1 = u \), \( a_k = v \), and for all \( 1 \le i < k \), \( (a_i, a_{i+1}) \in E \). The weight of the path is the sum of the weights of all its edges, i.e., \( \displaystyle \sum_{i=1}^{k-1} w(a_{i}, a_{i+1}) \).

A coloring scheme is considered good if and only if for every pair \( (u, v) \), all paths between \( u \) and \( v \) have weights that are congruent modulo \( 2 \).

Find the number of good coloring schemes, modulo \( (10^9 + 7) \).

Input Format

The first line contains two positive integers, \( N \) and \( M \), as described in the problem statement.

The next \( M \) lines each contain two positive integers \( u \) and \( v \), indicating \( (u, v) \in E \).

Output Format

Output a single integer, the answer modulo \( (10^9 + 7) \).

Sample Input and Output

Sample Input #1

4 4
1 2
2 3
3 4
1 4

Sample Output #1

8

Sample Input #2

4 4
1 3
1 4
2 3
2 4

Sample Output #2

16

Notes

Sample Explanation

Sample 1 Explanation: Clearly, there are two paths between \( 1 \) and \( 4 \): \( (1, 2, 3, 4) \) and \( (1, 4) \).

When \( w(1, 4) = 0 \), the path \( (1, 2, 3, 4) \) can have either \( 0 \) or \( 2 \) edges with weight \( 1 \), giving \( 4 \) schemes.

When \( w(1, 4) = 1 \), the path \( (1, 2, 3, 4) \) can have either \( 1 \) or \( 3 \) edges with weight \( 1 \), giving \( 4 \) schemes.

Thus, the answer is \( 8 \).

Data Range

For \( 100\% \) of the data, it is guaranteed that:

• \( 1 \le N \le 400 \), \( 0 \le M \le 400 \);
• \( 1 \le u < v \le n \).

见题面 Input 部分

见题面 Output 部分